| T(n) | category | How to Tell |
|---|---|---|
| O(logc n) | logarithmic | T(cn) ≈ T(n)+1 |
| O(n) | linear | T(cn)/T(n) ≈ c |
| O(n·logc n) | log-linear | T(cn)/T(n) ≈ c + c/logc n |
| O(n2) | quadratic | T(2n)/T(n) ≈ 4 |
| O(n3) | cubic | T(2n)/T(n) ≈ 8 |
| O(cn) | exponential | T(n+1) ≈ c·T(n) |
You will recall that the Fibonacci sequence is [0, 1, 1, 2, 3, 5, 8, 13, 21, ...] in which each element, other than the first two, is the sum of its two predecessors. Letting fib(n) refer to the n-th Fibonacci number in the sequence (counting starting at zero), we define fib(0) = 0, fib(1) = 1, and (for all n>1) fib(n) = fib(n−1) + fib(n−2).
Download the Fibonacci class. It includes methods fibA() and fibB() that use recursion to compute Fibonacci Numbers. The first one is complete, and its recursive code mimics the definition given above.
The class includes a main() method that allows a user to run experiments and get feedback on the "call count" and "max recursion depth". Run the program and have it compute several Fibonacci numbers. (Ignore the output referring to fibB().) Each time increase the argument by 1, as opposed to doubling it. Notice the ratio between successive call counts. Using the table above, try to discern fibA()'s asymptotic running time. Discuss it with your lab instructor.
Now turn your attention to the fibBAux() method, which is the "auxiliary" method used by fibB() that does all the real work. But it is going to do it in a much different fashion than fibA(), which by now you know is horribly inefficient.
The "trick" to be employed by fibBAux() —it is up to you to supply the missing code— is to pass back to its caller not just the n-th Fibonacci number but both the n-th and (n-1)-st. It does so by returning an array of length two, with fib(n−1) stored in location 0 and fib(n) stored in location 1.
Complete fibBAux(), run some tests, and compare the resulting call count values to those of fibA(). They should be MUCH, MUCH lower. Discuss it with your instructor.