**Example.** Suppose the running time of a function is
2^{n}. Further suppose that each primitive
operation can be executed in one micro second (i.e., 10^{-6}
seconds). Then solving the problem for `n` equals 100 will take
10^{-6}×2^{100} seconds. This equals
1.26765×10^{24} seconds, which is more than 10,000 trillion
years, more than the lifetime of the universe by several orders of magnitude.
You get the point. The function starts innocuously enough but grows
extremely rapidly and reaches astronomical proportions very quickly
and for a fairly small value of `n`.
Programs or functions whose running time is exponential can be useful
only for tiny inputs.

It turns out that the recursive fibonacci number function, given below, has running time that is exponential.

def fibonacci(n): if((n==1) or (n==2)): return 1 if(n > 2): return fibonacci(n-1) + fibonacci(n-2)Here is a figure (on the left) showing the

To estimate the running time of the function `fibonacci` when it
is called with arbitrary `n`, we first note that in order to do this
it is sufficient to simply count the total number of function calls
to `fibonacci` that are made.
When `n` equals 5, you can count the number of "nodes" in the
recursion tree on the left, to conclude that a total of
9 function calls were made.
It is sufficient to count the number of function calls because, the
running time of the function `fibonacci`, is a constant, *if we
exclude the time spent inside recursive calls*.

To count the number of nodes in the recursion tree corresponding to
`fibonacci(n)`, look at the shape of the recursion tree
on the right.
A level `i` is called *full* if it has 2^{i}
nodes in it.
In the recursion tree for `fibonacci(5)`, levels 0, 1, and 2
are full.
For the tree on the right, levels 0 through `n`/2-1 are all full.
Level `n`/2-1 has 2^{n/2-1} nodes.
Therefore the tree has at least 2^{n/2-1} nodes.
A bit of simplification shows that this is 1/2×SquareRoot(2)^{n}, which is roughly 1/2×(1.414)^{n}.
Note that this is an underestimate on the actual number of nodes in the tree,
but suffices to show that
the running time of the `fibonacci(n)` function is at least
exponential in `n`.

It is of course quite easy to see that the *iterative* fibonacci
function, shown below, runs in `O(n)` time.

def iterativeFibonacci(n): if((n==1) or (n==2)): return 1 previous = 1 current = 1 count = 2 while(count < n): temp = current current = current + previous previous = temp count = count + 1 return current