Assume that the cost of adding subtracting or multiplying

Question

The Fibonacci numbers are defined by the recurrence F0 = 0, F1 = 1

Fn = Fn-1 + Fn-2(n ≥ 2)

1. (a)  Show that Fn ≥ 2n/2, n ≥ 6.
2. (b)  Assume that the cost of adding, subtracting, or multiplying two integers is O(1), inde- pendent of the size of the integers.
   • Write pseudocode for an algorithm that computes Fn based on the recur- sive definition above. Develop a recurrence for the running time of your algorithm and give an asymptotic lower bound for it.
   • Write pseudocode for a non-recursive algorithm that asymptotically per- forms fewer additions than the recursive algorithm. Discuss the running time of the new algorithm.
   • Show how to compute Fn in O(log n) time using only integer additions and multiplications.
     (Hint: Express Fn in matrix notation and consider the matrix 0 1 11 and its powers.)
3. (c) Now assume that adding two m-bit integers requires Θ(m) time and that multiplying two m-bit integers requires Θ(m2) time. What is the running time of the three algorithms under this more reasonable cost measure for the elementary arithmetic operations?