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

¿Cuál es el valor de la siguiente recurrencia?

T(n) = T(n/4) + T(n/2) + cn2
T(1) = c
T(0) = 0

Donde c es una constante positiva

(A) O(n ³ )
(B) O(n ² )
(C) O(n ² Logn)
(D) O(nLogn)

Respuesta: (B)
Explicación: El siguiente es el árbol de recurrencia inicial para la relación de recurrencia dada .

           cn^2
         /      \
     T(n/4)     T(n/2)

Si desglosamos aún más la expresión T(n/4) y T(n/2), obtenemos el siguiente árbol de recurrencia.

               cn^2
           /           \      
       c (n^2)/16       c(n^2)/4
      /      \          /     \
  T(n/16)     T(n/8)  T(n/8)    T(n/4) 

Desglosar aún más nos da lo siguiente

                 cn^2
            /             \      
       c(n^2)/16           c(n^2)/4
       /      \            /      \
c(n^2)/256  c(n^2)/64  c(n^2)/64    c(n^2)/16
 /    \      /    \    /    \         /    \    
 

Para conocer el valor de T(n), necesitamos calcular la suma de los Nodes del árbol nivel por nivel. Si sumamos el árbol anterior nivel por nivel, obtenemos la siguiente serie
T(n) = c(n^2 + 5(n^2)/16 + 25(n^2)/256) + ….
La serie anterior es una progresión geométrica con una proporción de 5/16.
Para obtener un límite superior, podemos sumar la serie anterior para términos infinitos. Obtenemos la suma como (n^2) / (1 – 5/16) que es O(n^2)

Consulte la siguiente video conferencia para obtener más detalles.
http://www.youtube.com/watch?v=whjt_N9uYFI

Prueba de esta pregunta