Cover Data Structures and Algorithms with Object-Oriented Design Patterns in Java
next up previous contents index

Example-Computing Fibonacci Numbers

 

The Fibonacci numbers  are given by following recurrence

  equation32442

Section gif presents a recursive method to compute the Fibonacci numbers by implementing directly Equation gif. (See Program gif). The running time of that program is shown to be tex2html_wrap_inline67421.

In this section we present a divide-and-conquer style of algorithm for computing Fibonacci numbers. We make use of the following identities

gather32452

for tex2html_wrap_inline58520. (See Exercise gif). Thus, we can rewrite Equation gif as

  equation32460

Program gif defines the method fibonacci which implements directly Equation gif. Given n>1 it computes tex2html_wrap_inline59360 by calling itself recursively to compute tex2html_wrap_inline67433 and tex2html_wrap_inline67435 and then combines the two results as required.

   program32477
Program: Divide-and-conquer Example--computing Fibonacci numbers.

To determine a bound on the running time of the fibonacci method in Program gif we assume that T(n) is a non-decreasing function. That is, tex2html_wrap_inline67439 for all tex2html_wrap_inline58476. Therefore tex2html_wrap_inline67443. Although the program works correctly for all values of n, it is convenient to assume that n is a power of 2. In this case, the running time of the method is upper-bounded by T(n) where

  equation32486

Equation gif is easily solved using repeated substitution:

eqnarray32492

Thus, T(n)=2n-1=O(n).


next up previous contents index

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