7.4.5 Faster than Exponential Growth

We have already seen an example of a procedure that grows faster than exponentially in the size of the input: the fibo procedure at the beginning of this chapter! Evaluating an application of fibo involves $\Theta(\phi^n)$ recursive applications where $n$ is the magnitude of the input parameter. The size of a numeric input is the number of bits needed to express it, so the value $n$ can be as high as $2^b - 1$ where $b$ is the number of bits. Hence, the running time of the fibo procedure is in $\Theta(\phi^{2^b})$ where $b$ is the size of the input. This is why we are still waiting for (fibo 60) to finish evaluating.