Page 70 - INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS

INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS

C = (n-1) + 2*(n-1) / 2 + 4*(n-1) / 4+... (n-1) *(n-1) / (n-1),

lo cual es lo mismo que

C=(n-1) +(n-1) +…+(n-1).

Si se considera a cada uno de los componentes de la sumatoria como un término y el número de
términos de la sumatoria es igual a k (siendo k la profundidad del árbol binario recursivo), se tiene:

C = (n-1) *k.
Considerando que el número de términos de la sumatoria (k) es el número de niveles del árbol bina-
rio, el número de elementos del arreglo se puede definir como 2 = n, por esto,
k
Log 2 = log n, k log 2 = log n (recordando que log m=1), k =log n,
k
2 2 2 2 m 2

de ahí que la expresión anterior quede así:

C = (n-1) * log n
2

Otra forma de verlo es esta:

Cuando se realiza la llamada recursiva, una de las llamadas tomará el valor de k y la otra el valor de
n – k -1, por lo tanto:
T(n) = T(K) + T(n-k-1) + O (n).

En el peor caso se tiene cuando el arreglo está ordenado, por lo que k = 1 y la función llamada será
(n-1), (n-2)…2 (figura 2.4).

64