Expert: Zlatko - 9/7/2011

Question
Can you analyze the time complexity of the following programs.

1.

s=0 ; i=1;

while (s<n)
{
s+=i;
i+=2;
}

2.

s=0

for(i=1;i<=n;++i)
s+=i;

Answer
Hello Gurpreet
The first one is quite interesting. If you write out the values of s and i after each iteration of the loop, you will see that for every iteration of the loop, s grows as the square of the iteration count. This means that after the i'th iteration, s will be i squared. For s to get to n required about square root of n iterations, so the time complexity is O(square root of n).

The second one is not so interesting. For every iteration of the loop, i gets one step closer to n, so to get to n needs n iterations. The time complexity is O(n).

I hope that helps you out.