Answer Happy

The problem below was on the Midterm Examination. Both functions fi(n) and fa(n) compute the function f(n). a. Instead of using the functions f(n) or fu(nu), give a formula for the computation of f(n). (Hint: Develop a recurrence relation which satisfies the value of Son)) b. Write the code segment to compute f(n) using your formula from Parta. Can you compute f(n) in log(n) time?

b. Write the code segment to compute f(n) using your formula from Part a. Can you compute f(n) in log(n) time? 4. Consider the two functions below which both compute the value of f(n). The function fi was replaced with 12 because integer multiplications were found to take 4 times longer than integer additions (+). int fi(n: integer) int fan : : integer) if (n == 1) then return(1) if (n == 1) then return(1) else return(2*fi(n-1)); else return( S2(n -- 1) + S2(n-1)); i. Give a recurrence relation for fi which satisfies the number of multiplications ) executed as a function of n. ii. Solve the recurrence relation from Part i. iii. Give a recurrence relation for 82 which satisfies the number of additions (+) executed as a function of n. iv. Solve the recurrence relation from Part iii. v. Both functions compute the same functionſ. Was it a good idea to replace with ?