PUERTA | PUERTA-CS-2004 | Pregunta 85

Un programa toma como entrada un árbol de búsqueda binario balanceado con n Nodes hoja y calcula el valor de una función g(x) para cada Node x. Si el costo de calcular g(x) es min{no. de Nodes hoja en el subárbol izquierdo de x, no. de Nodes hoja en el subárbol derecho de x} entonces la complejidad temporal del programa en el peor de los casos es
(A) Θ(n)
(B) Θ(nLogn)
(C) Θ(n ² )
(D) Θ(n ² log n)

Respuesta: (B)
Explicación:

The recurrence relation for the recursive function is
T(N) = 2 * T(N/2) + n/2
Where N is the total no. of nodes in the tree.
T(N) = 2 * (2*T(N/2) + n/2) + n/2
     = 4 * T(N/2) + 3(n/2)
Solve this till T(1) i.e. till we reach the root.
T(N) = c * T(N / 2^i) + (2*i - 1) * (n/2)
Where i = lg(N)
= lg((2n - 1) / 2)
O(c * T(N / 2^i) + (2*i - 1) * (n/2)) reduces to
O((2*i - 1) * (n/2))
O((2*( lg((2n - 1) / 2)) - 1) * (n/2)) ...sub the value of i.
O(n * ln(n)) 

Fuente: http://www.nid.iitkgp.ernet.in/DSamanta/courses/IT60101_2/Archives/Assignment-%20IC%20Binary%20Trees%20Solutions.pdf
Prueba de esta pregunta