Question

1. Consider the following algorithm.

ALGORITHM Mystery(n)

//Input: A nonnegative integer n

S ! 0

for i !1 to n do

S ! S + i*i

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?

Please give as detailed an explanation as possible.

EXPERT ANSWER

GIven:

ALGORITHM Mystery(n)

//Input: A nonnegative integer n

S ! 0

for i !1 to n do

S ! S