Logo Data Structures and Algorithms with Object-Oriented Design Patterns in C++
next up previous contents index

Example-Fibonacci Numbers


In this section we will compare the asymptotic running times of two different programs that both compute Fibonacci numbers.gif The Fibonacci numbers  are the series of numbers tex2html_wrap_inline60409, tex2html_wrap_inline60411, ..., given by


Fibonacci numbers are interesting because they seem to crop up in the most unexpected situations. However, in this section, we are merely concerned with writing an algorithm to compute tex2html_wrap_inline60413 given n.

Fibonacci numbers are easy enough to compute. Consider the sequence of Fibonacci numbers


The next number in the sequence is computed simply by adding together the last two numbers--in this case it would be 55=21+34. Program gif is a direct implementation of this idea. The running time of this algorithm is clearly O(n) as shown by the analysis in Table gif.

Program: Non-recursive program to compute Fibonacci numbers



statement time
3 O(1)
4 O(1)
5a O(1)
5b tex2html_wrap_inline60427
5c tex2html_wrap_inline60429
7 tex2html_wrap_inline60429
8 tex2html_wrap_inline60429
9 tex2html_wrap_inline60429
11 O(1)
Table: Computing the running time of Program gif

Recall that the Fibonacci numbers are defined recursively: tex2html_wrap_inline60441. However, the algorithm used in Program gif is non-recursive --it is iterative . What happens if instead of using the iterative algorithm, we use the definition of Fibonacci numbers to implement directly a recursive algorithm ? Such an algorithm is given in Program gif and its running time is summarized in Table gif.

Program: Recursive program to compute Fibonacci numbers





n<2 tex2html_wrap_inline60445
3 O(1) O(1)
4 O(1) --
6 -- T(n-1)+T(n-2)+O(1)
TOTAL O(1) T(n-1)+T(n-2)+O(1)
Table: Computing the running time of Program gif

From Table gif we find that the running time of the recursive Fibonacci algorithm is given by the recurrence


But how do you solve a recurrence containing big oh expressions?

It turns out that there is a simple trick we can use to solve a recurrence containing big oh expressions as long as we are only interested in an asymptotic bound on the result. Simply drop the tex2html_wrap_inline58163s from the recurrence, solve the recurrence, and put the tex2html_wrap_inline58163 back! In this case, we need to solve the recurrence


In the previous chapter, we used successfully repeated substitution to solve recurrences. However, in the previous chapter, all of the recurrences only had one instance of tex2html_wrap_inline58299 on the right-hand-side--in this case there are two. There is something interesting about this recurrence: It looks very much like the definition of the Fibonacci numbers. In fact, we can show by induction on n that tex2html_wrap_inline60467.

extbfProof (By induction).

Base Case There are two base cases:


Inductive Hypothesis Suppose that tex2html_wrap_inline60469 for tex2html_wrap_inline60471 for some tex2html_wrap_inline59577. Then


Hence, by induction on k, tex2html_wrap_inline60469 for all tex2html_wrap_inline59063.

So, we can now say with certainty that the running time of the recursive Fibonacci algorithm, Program gif, is tex2html_wrap_inline60481. But is this good or bad? The following theorem shows us how bad this really is!

Theorem (Fibonacci numbers)     The Fibonacci numbers are given by the closed form expression


where tex2html_wrap_inline60483 and tex2html_wrap_inline60485.

extbfProof (By induction).

Base Case There are two base cases:


Inductive Hypothesis Suppose that Equation gif holds for tex2html_wrap_inline60471 for some tex2html_wrap_inline59577. First, we make the following observation:




Now, we can show the main result:


Hence, by induction, Equation gif correctly gives tex2html_wrap_inline60413 for all tex2html_wrap_inline59063.

Theorem gif gives us that tex2html_wrap_inline60495 where tex2html_wrap_inline60483 and tex2html_wrap_inline60485. Consider tex2html_wrap_inline60501. A couple of seconds with a calculator should suffice to convince you that tex2html_wrap_inline60503. Consequently, as n gets large, tex2html_wrap_inline60507 is vanishingly small. Therefore, tex2html_wrap_inline60509. In asymptotic terms, we write tex2html_wrap_inline60511. Now, since tex2html_wrap_inline60513, we can write that tex2html_wrap_inline60515.

Returning to Program gif, recall that we have already shown that its running time is tex2html_wrap_inline60481. And since tex2html_wrap_inline60515, we can write that tex2html_wrap_inline60521. I.e., the running time of the recursive Fibonacci program grows exponentially with increasing n. And that is really bad in comparison with the linear running time of Program gif!

Figure gif shows the actual running times of both the non-recursive and recursive algorithms for computing Fibonacci numbers.gif Because 32-bit unsigned integers are used, it is only possible to compute Fibonacci numbers up to tex2html_wrap_inline60525 before overflowing.

The graph shows that up to about n=35, the running times of the two algorithms are comparable. However, as n increases past 40, the exponential growth rate of Program gif is clearly evident. In fact, the actual time taken by Program gif to compute tex2html_wrap_inline60531 was in excess of one hour!

Figure: Actual Running Times of Programs gif and gif

next up previous contents index

Bruno Copyright © 1997 by Bruno R. Preiss, P.Eng. All rights reserved.