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_inline59637, tex2html_wrap_inline59639, ..., given by

  equation2055

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_inline59641 given n.

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

displaymath59631

The next number in the sequence is computed simply by adding together the last two numbers--in this case it is 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.

   program2064
Program: Non-recursive program to compute Fibonacci numbers.

 

 

statement time
5 O(1)
6 O(1)
7a O(1)
7b tex2html_wrap_inline59655
7c tex2html_wrap_inline59657
9 tex2html_wrap_inline59657
10 tex2html_wrap_inline59657
11 tex2html_wrap_inline59657
13 O(1)
TOTAL O(n)
Table: Computing the running time of Program gif.

Recall that the Fibonacci numbers are defined recursively: tex2html_wrap_inline59669. 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.

   program2095
Program: Recursive program to compute Fibonacci numbers.

 

 

time

statement

n<2 tex2html_wrap_inline59673
5 O(1) O(1)
6 O(1) --
8 -- 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

displaymath59632

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_inline57397s from the recurrence, solve the recurrence, and put the tex2html_wrap_inline57397 back! In this case, we need to solve the recurrence

displaymath59633

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_inline57533 on the right-hand-side--in this case there are two. As a result, repeated substitution won't work.

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_inline59695 for all tex2html_wrap_inline58277.

extbfProof (By induction).

Base Case There are two base cases:

eqnarray2125

Inductive Hypothesis Suppose that tex2html_wrap_inline59695 for tex2html_wrap_inline59701 for some tex2html_wrap_inline58801. Then

eqnarray2130

Hence, by induction on k, tex2html_wrap_inline59695 for all tex2html_wrap_inline58277.

So, we can now say with certainty that the running time of the recursive Fibonacci algorithm, Program gif, is tex2html_wrap_inline59711. 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

  equation2144

where tex2html_wrap_inline59713 and tex2html_wrap_inline59715.

extbfProof (By induction).

Base Case There are two base cases:

eqnarray2156

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

eqnarray2170

Similarly,

eqnarray2174

Now, we can show the main result:

eqnarray2180

Hence, by induction, Equation gif correctly gives tex2html_wrap_inline59641 for all tex2html_wrap_inline58277.

Theorem gif gives us that tex2html_wrap_inline59725 where tex2html_wrap_inline59713 and tex2html_wrap_inline59715. Consider tex2html_wrap_inline59731. A couple of seconds with a calculator should suffice to convince you that tex2html_wrap_inline59733. Consequently, as n gets large, tex2html_wrap_inline59737 is vanishingly small. Therefore, tex2html_wrap_inline59739. In asymptotic terms, we write tex2html_wrap_inline59741. Now, since tex2html_wrap_inline59743, we can write that tex2html_wrap_inline59745.

Returning to Program gif, recall that we have already shown that its running time is tex2html_wrap_inline59711. And since tex2html_wrap_inline59745, we can write that tex2html_wrap_inline59751. That is, 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 the largest C# int is 2147483647, it is only possible to compute Fibonacci numbers up to tex2html_wrap_inline59755 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_inline59761 was in excess of two and a half minutes!

   figure2233
Figure: Actual running times of Programs gif and gif.


next up previous contents index

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