Time complexity of functions

Question

What's the time complexity of the following two functions?

int fun1(int n){
if(n>0)
return (2*fun1(n-1)+1);
else return 1;
}

int fun2(int n){
if(n>0)
return (fun2(n-1)+fun2(n-1)+1);
else return 1;
}

Obviously for fun2 we write recursive equation as T(n) = 2*T(n-1) + 1 but how do we write recursive equation for fun1?

Answer 1

You're correct about fun2.

For fun1, think about your usual rules of math, disregard time complexity. 2*fun1(n-1) = fun1(n-1) + fun1(n-1), unless rules of multiplication can redefined, such as in modern analysis (I believe that's the vein of mathematics that's taught in. Been a while since I was in that class :) )

So with the distribution rule, fun1 is effectively the same as fun2, thus having the same time complexity.

Answer 2

Just a quick look at the code (I may be wrong). The fun1 has the O(n) time complexity (linear), the fun2 has O(2^n) time complexity (exponential).

When you imagine levels of recursion, then one depth level doubles the number of recursive calls. So, for n == 10, there is one call of fun2(10), and then there are 2 calls of fun2(9), 4 calls of fun2(8), 8 calls of fun2(7), 16 for 6, 32 for 5, 64 for 4, 128 for 3, 256 for 2, 512 for 1, 1024 calls fun2(0). The last mentioned just return 1.

This is a nice example that you should always think twice when implementing functions like that using recursion. A simple fix (the 2*fun2(n-1) instead of fun2(n-1) + fun2(n-1)) makes it O(n).

This also explains why Fibonacci numbers should not be implemented using naive recursion. Frankly, simple loop without any recursion is much better in the case.

So, the equation for calculating the time complexity should contain 2^something + something. ;)