Question

Answer the four questions below:

ALGORITHM Mystery(n)

//Input: A nonnegative integer n

S <– 0

for i <– 1 to n do

S <– S + i * i

return S

What does this algorithm compute?

What is its basic operation?

How many times is the basic operation executed? (Solve the summation.)

What is the efficiency of this algorithm? (Expressed in the proper notation.)

EXPERT ANSWER

This algorithm computes the sum of ‘squares of numbers’ from 1 to n, i.e.,

*S* =