CODEWITHSUNDEEP
algorithmtime-complexitymaster-theorem
Avenash
Avenash

Reputation: 85

What will be the time complexity of following recursive algorithm?

What will be the complexity of following recursive algorithm? 

void rec(n){
 if(n<=0)
    return;
 else
    rec(n/3)+rec(n/2); 
}

Upvotes: 3

Views: 158

Answers (1)

BishalG
BishalG

Reputation: 1434

The time complexity of above program is O(2 ^ k), where k is depth of recursion. Here, 2 arises from the fact that in each recursive calls we are giving calls to 2 other recursive calls. Now, lets analyze the deepest depth of recursion (k).

enter image description here

In above figure, the recursive path dividing by 2 in each step will take longer time to reach its value less than 1 (which is base case) and hence it will be the deepest depth of recursion. Since, every time we are dividing n by 2. It will take log steps to reach less than 1. Although we also divide n by 3. Dividing n by 2 will take longer time and hence responsible as a deciding factor for deepest depth of recursion. For details:

In 1st call, we reduce n by n / 2.
In 2nd call, we reduce n by (n / 2) / 2 = n / 4 = n / 2^2.
Hence, In Kth step, we reduce n by : n / 2^k = 1.
So, n = 2 ^ k.

Taking log base 2 on both sides,

log2 n = log2 (2^k)
log2 n = k log2(2)
log2 n = k * 1 [ since, log2(2) is 1 ]

Therefore, In a deepest depth of recursion, we need k = log(n) steps to reach n = 1 and one more step to reach n <= 0. But, overall the depth of recursion will be in between log3 n to log2 n.

So, overall time complexity is O(2 ^ log n) in worst case scenario. But, Since we also divide n by 3 and hence all recursive path depth starting from top to leaf node will not be same as that of log n. Hence, we can conclude time complexity as O(2 ^ k), where k is depth of recursion.

Upvotes: 4

Related Questions