PUERTA | PUERTA-CS-2002 | Pregunta 3 – Part 3

La solución a la ecuación de recurrencia T(2 ^k ) = 3 T(2 ^k-1 ) + 1, T (1) = 1, es:
(A) 2 ^k
(B) (3 ^{k + 1} – 1)/2
(C) 3 ^log 2k
(D) 2 ^log 3k

Respuesta: (B)
Explicación: Tenemos

T (2 ^k ) = 3 T (2 ^k-1 ) + 1

= 3 ²   T (2 ^k-2 ) + 1 + 3
= 3 ³   T (2 ^k-3 ) + 1 + 3 + 9
. . . (k pasos de recursión (profundidad de recursión))
= 3 ^k   T (2 ^k-k ) + (1 + 3 + 9 + 27 + … + 3 ^k-1 )
= 3 ^k + ( ( 3 ^k – 1 ) / 2 )
= ( (2 * 3 ^k ) + 3 ^k – 1 )/2
= ( (3 * 3 ^k ) – 1 ) / 2
= (3 ^k+1 – 1) / 2

Por lo tanto, B es la opción correcta.

Comente a continuación si encuentra algo incorrecto en la publicación anterior.
Cuestionario de esta pregunta