ISRO | CS ISRO 2015 | Pregunta 40

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

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

(A) O(n)
(B) O(n log n)
(C) O(n ² )
(D) O(2 ⁿ )

Respuesta: (D)
Explicación: Relación de recurrencia para el código = T(n) = 2T(n-1) + k.
Podemos resolver la recurrencia usando el método de sustitución:

T(n) = 2T(n-1) + k
     = 2(2T(n-2) + k) + k
     = 2(2(2T(n-3) + k) + k) + k.....
     = 2xT(n-x) + 2(1 + 2 +....+ 2x-1)k
When base condition is met, i.e. n=1, x=n-1
     = 2n-1 T(1) + k(2n)
     = O(2n)

Entonces, la opción (D) es correcta.
Cuestionario de esta pregunta