Hasta aquí las funciones bajaban de una en una. Esta parte el rango por la mitad y se llama dos veces, y el proceso deja de ser una fila para volverse un árbol. Se dibuja un nodo por paso, en el orden en que las llamadas ocurren: primero la rama izquierda hasta el fondo, después la derecha.
producto se hacen en total?Para n números hay n
hojas y n − 1 nodos que parten: 2n − 1 llamadas.
Es más que las n + 1 de la versión lineal, así que en
tiempo no se ganó nada.
Lo que cambió es cuántas de esas llamadas están abiertas a la
vez. La versión lineal las abre todas antes de cerrar la primera:
n + 1 marcos. El árbol cierra la rama izquierda entera antes
de abrir la derecha, así que en la pila nunca hay más que un camino de la
raíz a una hoja: tantos marcos como niveles, ⌈log₂ n⌉ + 1.
Para n = 1024, once en vez de mil y veinticinco.
Las dos predicciones dan números distintos porque miden cosas distintas: las llamadas son el tiempo, los marcos abiertos al tiempo son el espacio.
El siguiente ejercicio pone los tres procesos en una tabla, para compararlos con los mismos números.