Consider the following algorithm: ALGORITHM S(n)//Input: A positive integer n//o

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.

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.