Problem Statement Read and understand “The Bigger Picture” section on page 337 o

Question

Problem Statement

Read and understand “The Bigger Picture” section on page 337 on The book "Java Programming: From The Ground Up (1st Edition). Be ready to explain why or how the various solutions are different. After you get the code for “public class FibTester”, which starts on page 341 to work, experiment with different numbers (I recommend keeping n<=50). Copy paste your programs printed result into Excel. Use Excel to subtract the start time from the end time and calculate the time each version took. Sample is shown below. Explain how everything works step by step.

THE BIGGER PICTURE THE COMPLEXITY OF RECURSIVE ALGORITHMS The complexity of an algorithm is synonymous with the speed of an algorithm. Does the algorithm run efficiently, that is, quickly, or not? The faster a program runs, the better; and behind every fast program there is an efficient algorithm. When designing a recur- sive algorithm, it is not only correctness that is important, but efficiency. Let's look at an example. The Fibonacci numbers comprise the infinite sequence: 1, 1. 2, 3. 5, 8, 13, 21. 34, 55, 89, and so on, in which each number (except the first two) is the sum of the previous two numbers. In computer science, Fibonacci numbers have many applications ranging from data structures (Fibonacci heaps) to pseudo-random number generators (lagged Fibonacci generators). Fibonacci numbers also manifest themselves in leaf arrangements, seashells, pine cones, and sunflower seeds. The sunflower in Figure 8.14, for example, has 21 and 34 spirals of seeds, one set curving right and one set curving left. Note that 21 and 34 are the 10th and 11th Fibonacci numbers.

Explanation / Answer

The answer is pretty much in the given question itself. Starts with "A glaring inefficiency that you should notice...." However to make you understand better, I'm writing the below answer in simplified terms.

Algorithm 1 & 3 are same (semantically) and also in terms of complexity.

Working of algo1 (fib1)

It all starts with number 1 and 2.

1 + 2 = 3 is the next fib number achived by simply hardcoding (initializing) the first 2 numbers.

Thereafter previous 2 numbers are stored in variables highest (3) and next_highest (2) and then sum of those two will be calculated in a loop for desired number of times. 2 + 3 = 5 (next fib number).

Similary 5 + 3 = 8 (next fib number).

Here, you are making use of results of previous fib number (which are already computed) and avoiding any recomputation (except 1 addition per fib number).

Algo3 - it is just a recursive version of algo1.

Coming to algo2 (fib2), it essentially calculates fib of a number by summing up fib of previous number and fib of 2nd previous number. A point to note here is that every time it calculates fib of a number, it needs to calculate fib of previous 2 numbers which inturn uses the same fib alogrithm.

Suppose you want to calcualte fib(6), logic is

fib(6) = fib(5) + fib(4)

fib(5) = fib(4) + fib(3) will be calculated separately for fib(5) (1st parameter) and

for fib(4) = fib(3) + fib(2) will be calculated separately for fib(4) (2nd parameter)

Notice even though fib(4) is computed for 2nd parameter, it again needs to be recomputed for fib(5) as well since we are not storing any fib computation values. Now imagine this for larger numbers ! This is the reason, the time taken for larger numbers increases exponentially.

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.