ISRO | CS ISRO 2017 | Pregunta 18

Considere la ecuación de recurrencia

T(n) = 2T(n-1), if n>0
     = 1, otherwise

Entonces T(n) es (en orden O grande)
(A) O(n)
(B) O(2 ⁿ )
(C) O(1)
(D) O(log n)

Respuesta: (B)
Explicación: Usando Método de sustitución:
$T(n) = 2T(n-1)$
$= 2(2T(n-2)) = 2^2T(n-2)$
$= 2(2^2T(n-2)) = 2^3T(n-3)$
$....$
$= 2(2^{n-3}T(n-(n-2))) = 2^{n-2}T(n-(n-2))$
$= 2(2^{n-2}T(n-(n-1))) = 2^{n-1}T(n-(n-1)) = 2^{n-1}T(1)$
$= 2(2^{n-1}T(n-(n))) = 2^{n}T(n-(n)) = 2^{n}T(0)$
$T(n) = O(2^n)$