Recurrences 4. Fibonacci number is defined as follows F(n)=0forn=0=1forn=1=F(n1)+F(n2)otherwise. (a) (5) Complete the following pseudocode for computing Fibonacci numbers for n0. FIBONACCI (n) If n1 Return ? Else Return? + ? (b) (10) write a recurrence for the number of additions performed by the above algorithm and show the above design takes exponential running time. (c) (10) Assume that the cost of adding two numbers is O(1). Show how to compute F(n) in O(n) time given sufficient memory