Algoritmos | Análisis de Algoritmos (Recurrencias) | Pregunta 11 – Part 1

Considere la siguiente recurrencia:

gate_2006_51

¿Cuál de las siguientes es verdadera?

(A) T(n) = \ theta(loglogn)
(B) T(n) = \ theta(logn)
(C) T(n) = \ theta(raíz cuadrada(n))
(D) T(n) = \ theta(n)

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

Respuesta: (B)
Explicación: Esta pregunta se puede resolver primero cambiando la variable y luego el Método Maestro.

  Let n = 2^m
  T(2^m) = T(2^(m/2)) + 1
  Let T(2^m) =  S(m)
  S(m)  = 2S(m/2) + 1  

La expresión anterior es una recursión transversal de un árbol binario cuya complejidad temporal es \ theta(m). También puedes probar usando el teorema de Master .

S(m)  = \theta(m)  
      = \theta(logn)  /* Since n = 2^m */

Ahora, volvamos a la función recursiva original T(n)

  T(n)  = T(2^m) = S(m)
                 = \theta(Logn)

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *