GATE Exam | Aptitude Questions | GATE Syllabus | GATE Result | Mock Test | GATE Preparation
0 votes
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));

}
asked in data structures and algorithms by gate

1 Answer

0 votes

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)
answered by gate

Related questions

The best answer to any question