y 2.5 Example: Computing the nth Fibonacci Number In this section, we consider the Fibonacci numbers, a famous sequence 0, 1, 1, 2, 3, 5, 8, 13, 21, 34,... (2.5) that can be defined by the simple recurrence F (n) = F (n − 1) + F (n − 2) for n > 1 (2.6) and two initial conditions F (0) = 0, F(1) = 1. (2.7) The Fibonacci numbers were introduced by Leonardo Fibonacci in 1202 as a solution to a problem about the size of a rabbit population (Problem 2 in this section’s exercises). Many more examples of Fibonacci-like numbers have since been discovered in the natural world, and they have even been used in predicting the prices of stocks and commodities. There are some interesting applications of the Fibonacci numbers in computer science as well. For example, worst-case inputs for Euclid’s algorithm discussed in Section 1.1 happen to be consecutive elements of the Fibonacci sequence. In this section, we briefly consider algorithms for computing the nth element of this sequence. Among other benefits, the discussion will provide us with an opportunity to introduce another method for solving recurrence relations useful for analysis of recursive algorithms. To start, let us get an explicit formula for F (n). If we try to apply the method of backward substitutions to solve recurrence (2.6), we will fail to get an easily discernible pattern. Instead, we can take advantage of a theorem that describes solutions to a homogeneous second-order linear recurrence with constant coefficients ax(n) + bx(n − 1) + cx(n − 2) = 0, (2.8) where a, b, and c are some fixed real numbers (a = 0) called the coefficients of the recurrence and x(n) is the generic term of an unknown sequence to be found. Applying this theorem to our recurrence with the initial conditions given—see Appendix B—we obtain the formula F (n) = 1 √ 5 (φn − φˆn), (2.9) where φ = (1 + √ 5)/2 ≈ 1.61803 and φˆ = −1/φ ≈ −0.61803.6 It is hard to believe that formula (2.9), which includes arbitrary integer powers of irrational numbers, yields nothing else but all the elements of Fibonacci sequence (2.5), but it does! One of the benefits of formula (2.9) is that it immediately implies that F (n) grows exponentially (remember Fibonacci’s rabbits?), i.e., F (n) ∈ (φn). This 6. Constant φ is known as the golden ratio. Since antiquity, it has been considered the most pleasing ratio of a rectangle’s two sides to the human eye and might have been consciously used by ancient architects and sculptors.2.5 Example: Computing the nth Fibonacci Number 81 follows from the observation that φˆ is a fraction between −1 and 0, and hence φˆn gets infinitely small as n goes to infinity. In fact, one can prove that the impact of the second term √ 1 5 φˆn on the value of F (n) can be obtained by rounding off the value of the first term to the nearest integer. In other words, for every nonnegative integer n, F (n) = 1 √ 5 φn rounded to the nearest integer. (2.10) In the algorithms that follow, we consider, for the sake of simplicity, such operations as additions and multiplications at unit cost. Since the Fibonacci numbers grow infinitely large (and grow very rapidly), a more detailed analysis than the one offered here is warranted. In fact, it is the size of the numbers rather than a time-efficient method for computing them that should be of primary concern here. Still, these caveats notwithstanding, the algorithms we outline and their analysis provide useful examples for a student of the design and analysis of algorithms. To begin with, we can use recurrence (2.6) and initial conditions (2.7) for the obvious recursive algorithm for computing F (n). ALGORITHM F (n) //Computes the nth Fibonacci number recursively by using its definition //Input: A nonnegative integer n //Output: The nth Fibonacci number if n ≤ 1 return n else return F (n − 1) + F (n − 2) Before embarking on its formal analysis, can you tell whether this is an efficient algorithm? Well, we need to do a formal analysis anyway. The algorithm’s basic operation is clearly addition, so let A(n) be the number of additions performed by the algorithm in computing F (n). Then the numbers of additions needed for computing F (n − 1) and F (n − 2) are A(n − 1) and A(n − 2), respectively, and the algorithm needs one more addition to compute their sum. Thus, we get the following recurrence for A(n): A(n) = A(n − 1) + A(n − 2) + 1 for n > 1, (2.11) A(0) = 0, A(1) = 0. The recurrence A(n) − A(n − 1) − A(n − 2) = 1 is quite similar to recurrence F (n) − F (n − 1) − F (n − 2) = 0, but its right-hand side is not equal to zero. Such recurrences are called inhomogeneous. There are general techniques for solving inhomogeneous recurrences (see Appendix B or any textbook on discrete mathematics), but for this particular recurrence, a special trick leads to a faster solution. We can reduce our inhomogeneous recurrence to a homogeneous one by rewriting it as [A(n) + 1] − [A(n − 1) + 1] − [A(n − 2) + 1] = 0 and substituting B(n) = A(n) + 1:82 Fundamentals of the Analysis of Algorithm Efficiency B(n) − B(n − 1) − B(n − 2) = 0, B(0) = 1, B(1) = 1. This homogeneous recurrence can be solved exactly in the same manner as recurrence (2.6) was solved to find an explicit formula for F (n). But it can actually be avoided by noting that B(n) is, in fact, the same recurrence as F (n) except that it starts with two 1’s and thus runs one step ahead of F (n). So B(n) = F (n + 1), and A(n) = B(n) − 1 = F (n + 1) − 1 = 1 √ 5 (φn+1 − φˆn+1 ) − 1. Hence, A(n) ∈ (φn), and if we measure the size of n by the number of bits b = log2 n + 1in its binary representation, the efficiency class will be even worse, namely, doubly exponential: A(b) ∈ (φ2b ). The poor efficiency class of the algorithm could be anticipated by the nature of recurrence (2.11). Indeed, it contains two recursive calls with the sizes of smaller instances only slightly smaller than size n.(Have you encountered such a situation before?) We can also see the reason behind the algorithm’s inefficiency by looking at a recursive tree of calls tracing the algorithm’s execution. An example of such a tree for n = 5 is given in Figure 2.6. Note that the same values of the function are being evaluated here again and again, which is clearly extremely inefficient. We can obtain a much faster algorithm by simply computing the successive elements of the Fibonacci sequence iteratively, as is done in the following algorithm. ALGORITHM Fib(n) //Computes the nth Fibonacci number iteratively by using its definition //Input: A nonnegative integer n //Output: The nth Fibonacci number F[0]← 0; F[1]← 1 for i ← 2 to n do F[i]← F[i − 1] + F[i − 2] return F[n] F(3) F(4) F(5) F(3) F(2) F(2) F(1) F(2) F(1) F(1) F(0) F(1) F(0) F(1) F(0) FIGURE 2.6 Tree of recursive calls for computing the 5th Fibonacci number by the definition-based algorithm.2.5 Example: Computing the nth Fibonacci Number 83 This algorithm clearly makes n − 1 additions. Hence, it is linear as a function of n and “only” exponential as a function of the number of bits b in n’s binary representation. Note that using an extra array for storing all the preceding elements of the Fibonacci sequence can be avoided: storing just two values is necessary to accomplish the task (see Problem 8 in this section’s exercises). The third alternative for computing the nth Fibonacci number lies in using formula (2.10). The efficiency of the algorithm will obviously be determined by the efficiency of an exponentiation algorithm used for computing φn. If it is done by simply multiplying φ by itself n − 1 times, the algorithm will be in (n) = (2b). There are faster algorithms for the exponentiation problem. For example, we will discuss (log n) = (b) algorithms for this problem in Chapters 4 and 6. Note also that special care should be exercised in implementing this approach to computing the nth Fibonacci number. Since all its intermediate results are irrational numbers, we would have to make sure that their approximations in the computer are accurate enough so that the final round-off yields a correct result. Finally, there exists a (log n) algorithm for computing the nth Fibonacci number that manipulates only integers. It is based on the equality F (n − 1) F (n) F (n) F (n + 1) = 0 1 1 1 n for n ≥ 1 and an efficient way of computing matrix powers.