Answer Happy

4. Consider the two functions below which both compute the value of f(n). The function fi was replaced with f2 because integer multiplications (*) were found to take 4 times longer than integer additions (+). int fi(n: integer) int f2(n: integer) if (n == 1) then return(1) if (n == 1) then return(1) else return(2 * fi(n-1)); else return(12(n − 1) + f2(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 f2 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 f. Was it a good idea to replace f1 with f2?