4. Consider the two functions below which both compute the value of f(n). The function fi...

Transcribed Image Text:

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) if (n == 1) then return(1) else return(2 fi(n-1)); int f2(n: integer) if (n == 1) then return(1) else return(f2(n-1) + f2(n-1)); i. Give a recurrence relation for f₁ 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 fi with f2? 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) if (n == 1) then return(1) else return(2 fi(n-1)); int f2(n: integer) if (n == 1) then return(1) else return(f2(n-1) + f2(n-1)); i. Give a recurrence relation for f₁ 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 fi with f2?

Answer rating: 100% (QA)

i Recurrence Relation for f which satisfies the number of multiplications T Tn 1 1 ... View the full answer