3.2. Análisis de tiempos de ejecución.
En general, si el problema se divide en a llamadas recursivas de tamaño n/b, y la combinación requiere f(n) = d·n ? O(n), entonces:
t(n) = a·t(n/b) + d·n
Suponiendo n = bk ? k = logb n
t(bk) = a·t(bk-1) + d·bk
Podemos deducir que:
O(nlogba) Si a > b
t(n) ? O(n·log n) Si a = b
O(n) Si a < b
Ejemplo 3. Dividimos en 2 trozos de tamaño n/2:
a = b = 2
t(n) ? O(n·log n)
Ejemplo 4. Realizamos 4 llamadas recursivas con trozos de tamaño n/2.
a = 4; b = 2
t(n) ? O(nlog24) = O(n2)
Según esto, ¿cuál es el tiempo para un recorrido en un árbol binario?
¿Cuál sería el tiempo si g(n) ó f(n) fueran polinomios de grado p?