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.
Para el nivel resaltado elija cuántos nodos tiene, cuánto trabaja cada uno y cuánto cuesta el nivel entero.
| nivel | cada nodo | nodos | trabajo por nodo | costo 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?
¿Cuántos niveles tiene el árbol?
¿Cuánto suma todo, en unidades de c?
Desarrollando la recurrencia por sustitución:
Con el total en función de n, ¿a qué clase pertenece T(n)?