Consider the following algorithm: ALGORITHM S(n)//Input: A positive integer n//o
ID: 3808450 • Letter: C
Question
Consider the following algorithm: ALGORITHM S(n)//Input: A positive integer n//output: The sum of the first n cubes if (n 1) return 1 else return S (n-1) + n*n*n a. Set up a recurrence relation, M(n), for the number of multiplications made by the algorithm. b. Solve the recurrence relation using Substitution (Iteration) method Assume M(1) = 0. c. Write a non-recursive, straightforward algorithm for computing the above algorithm. d. Compare the number of multiplication performed by the non-recursive algorithm with the recursive algorithm. Explain your observation.Explanation / Answer
4 a. M(n) = M(n-1) + 2; M(1) = 0;
b. M(n) = M(n-2) + 2 + 2 = M(n-2) + 2*2
M(n) = M(n-3) + 2+ 2*2 = M(n-3) + 3*2
M(n) = M(n-(n-1)) + (n-1)*2
M(n) = M(1) + 2n -2
M(n) = 2n-2
c.
Algorithm2 S(n)
// Input: A positive integer n
// Output: The sum of first n cubes
sum = 1
for i = 2 to n
sum += i*i*i
return sum
d. Number of multiplication performed by both algorithm is same.