Considere la siguiente recurrencia:
¿Cuál de las siguientes es verdadera?
(A) T(n) =
(registro)
(B) T(n) =
(registro)
(C) T(n) =
(raíz cuadrada(n))
(D) T(n) =
(n)
(A) A
(B) B
(C) C
(D) D
Respuesta: (B)
Explicación:
Antecedentes requeridos: resolución de recurrencia mediante el método de sustitución.
Respuesta – B
Desplegando la recursividad,
T(n) = 2T(n^(1/2)) + 1
= 2^2T(n^(1/4)) + 2
= 2^3T(n^(1/8)) + 3
.
. k pasos
.
= 2^kT(n^(1/2k)) + k …………. (1)
Usando el caso base,
n^(1/2k) = 2
Tomando log en ambos lados
log2n = 2k
k = log2log2n
De 1),
T(n) = log2n + log2log2n
= Theta(log2n)
Aquí log2n : log(base 2) n
Relacionado:
http://geeksquiz.com/algorithms-analysis-of-algorithms-question-17-2/
Esta solución es aportada por .
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA