The time complexity of the following C function is (assume n > 0 (GATE CS 2004)

int recursive (mt n)

{

if (n == 1)

return (1);

else

return (recursive (n-1) + recursive (n-1));

}

Recursive expression for the above program will be.

  T(n) = 2T(n-1) + c
T(1) = c1.

Let us solve it.

  T(n) = 2(2T(n-2) + c) + c        = 4T(n-2) + 3c
T(n) = 8T(n-3) + 6c + c          =  8T(n-3) + 7c
T(n) = 16T(n-4) + 14c + c        =  16T(n-4) + 15c

T(n) = (2^(n-1))T(1) +  (2^(n-1) - 1)c

T(n) = O(2^n)