Question

Consider the following algorithm:

ALGORITHM Mystery(n) //Input: A nonnegative integer n for ← 1 to n do return S

a. What does this algorithm compute?

b. Compute the running time of this algorithm.

Answer 1

a) Lets trace The algorithm for n = 5;

The for loop wil go from i = 1 to i=5;

So at start S = 0;

then for i=1, S = S + 1*1 = 1
for i=2, S= S + 2*2 = 5
for i=3, S = S + 3*3 = 14
for i=4, S=S+4*4 = 30
for i=5; S = S+5*5 = 55

So At the end, S is nothing but sum of squares from numbers from 1 to n..
55 = 1^2 + 2^2 + 3^2 + 4^2 + 5^2

So algorithm computes sum of squares of first n numbers.

b) The running time of the algorithm:

As the for loop will run once for each of the numbers starting from 1 till n, hence the for loop will be running for n times.. Hence the running time of O(n)
In the above example, you can verify that the loop ran for 5 times for n=5.