This problem compares the efficiency of three methods for computing the nth Fibonacci number F_n, given n. Assume that the cost of adding, subtracting, or multiplying two numbers is O(1), independent of the size of the numbers.

a. Show that the running time of the straightforward recursive method for computing F_n based on recurrence (3.22) is exponential in n. 

b. Show how to compute F_n in O(n) time using memoization.

c. Show how to compute F_n in O(lg n) time using only integer addition and multiplication.

d. Assume now that adding two β-bit numbers takes Θ(β) time and that multiplying two β-bit numbers takes ‚(β²) time. What is the running time of these three methods under this more reasonable cost measure for the elementary arithmetic operations?