Algoritmos | Análisis de Algoritmos (Recurrencias) | Pregunta 9

La complejidad temporal de la siguiente función C es (suponga que n > 0 (GATE CS 2004)

int recursive (mt n)
{
   if (n == 1)
     return (1);
   else
     return (recursive (n-1) + recursive (n-1));
}

(A) 0(n)
(B) 0(nlogn)
(C) 0(n^2)
(D) 0(2^n)

Respuesta: (D)
Explicación: La expresión recursiva para el programa anterior será.

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

Vamos a resolverlo.

  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)

Cuestionario de esta pregunta