7. Textbook, exercise 2.3 (page #67): Questions: #4. (25 points) Consider the fo

Question

7. Textbook, exercise 2.3 (page #67): Questions: #4. (25 points) Consider the following algorithm. Algorithm Mystery (n) Input: A nonnegative integer n fori 1 to n do return S a. What does this algorithm compute? b. What is its basic operation? c. How many times is the basic operation executed? d. What is the efficiency class of this algorithm? e, suggest an improvement or a better algorithm altogether and indicate its efficiency lf you cannot do it, try to prove that, in fact, it cannot be done.

Explanation / Answer

(a)
The algorithm computes the sum of squares of natural numbers from 1 to n

(b)
addition

(c)
The basic operation is executed n times

(d)
The efficiency is theta(n)

(e)
Algorithm Mystry1(n)
   // Input: A nonnegative integer n
   S <- 0
   S = n * (n + 1) * (2n + 1) / 6
   return S

Its efficiency is theta(1) as it does not depend on n

Related Questions

Navigate

• Browse (All)
• Browse 7
• Subjects

---

---

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