Algoritmos | Análisis de Algoritmos (Recurrencias)

Considere la siguiente recurrencia.

T(n) = T( $\sqrt{n}$ ) + $\Theta(Registro Registro n)$

¿Cuál es el valor de la recurrencia?

(A) $\Theta( (Registro Registro n) ^ 2)$
(B) $\Theta(Registro Registro n)$
(B) $\Theta(n)$
(B) $\Theta(Registro Registro Registro n)$

(A) A
(B) B
(C) C
(D) D

Respuesta: (A)
Explicación: Cambio de variables: sea m = lg n. La recurrencia se convierte en S(m) = S(m/2) + theta(lgm). Se aplica el caso 2 del teorema de Master, por lo que T(n) = theta((log Log n) ^ 2).
Cuestionario de esta pregunta

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

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

Deja una respuesta Cancelar la respuesta