Question 4: The function f : {0,1,2,...} → R is defined byf(0) = 7,
f(n) = 5·f(n−1)+12n2 −30n+15 ifn≥1.• Prove that for every integer n ≥ 0,
f(n)=7·5n −3n2.
Question 5: Consider the following recursive algorithm, which takes
as input an integer
n ≥ 1 that is a power of two:
Algorithm Mystery(n):
if n = 1
then return 1
else x = Mystery(n/2);
return n + xendif
• Determine the output of algorithm Mystery(n) as a function of n. As always, justify your answer.
Get Answers For Free
Most questions answered within 1 hours.