CODEWITHSUNDEEP
recursiontime-complexitycomplexity-theory
Achraf
Achraf

Reputation: 357

complexity of recersive function nestedin a loop

Im trying to calculate the complexity of a recursive call inside a loop: 

Calculate(n,m){
for(i=1; i<n; i++){
    if(n==1) return 1;
    Calculate(n-1,m);
 }
for(j=1; i<m; i++){
    Calculate(n,m-1);
    if(m==1) return 1;
} 
}

here is what i did to calculate it : 

C(m,n) = 1 + C(m-1,n) + C(m-2,n) + .... + C(1,n) 
           + C(m,n-1) + C(m,n-2) + .... + C(m,1)

is the complexity = 2^(m+n) ??

Upvotes: 0

Views: 46

Answers (1)

Ken Wei
Ken Wei

Reputation: 3130

You are correct: to reduce either m or n by 1, you need to make 2 calls; since you need to reduce both of them to zero, you need to go through O(m+n) 'levels'.

Thus the number of calls is O(2^(m+n)).

Upvotes: 1

Related Questions