← Volver a los ejercicios

arbol: el costo de una recurrencia, nivel por nivel

Cada nodo del árbol es una llamada y lleva el trabajo que esa llamada hace fuera de sus llamadas recursivas. Sumando por niveles se obtiene T(n) sin desarrollar la recurrencia; después se comparan los dos caminos. El trabajo se escribe en unidades de c.

1. La recurrencia y el tamaño

2. Nivel por nivel

Para el nivel resaltado elija cuántos nodos tiene, cuánto trabaja cada uno y cuánto cuesta el nivel entero.

nivelcada nodonodostrabajo por nodocosto del nivel

¿Cuántos nodos tiene el nivel?

¿Cuánto trabaja cada nodo, en unidades de c?

¿Cuánto cuesta el nivel entero, en unidades de c?

3. Niveles y total

¿Cuántos niveles tiene el árbol?

¿Cuánto suma todo, en unidades de c?

Desarrollando la recurrencia por sustitución:

4. La clase Θ

Con el total en función de n, ¿a qué clase pertenece T(n)?