You are here:

- Home
- Computing/Technology
- C/C++
- C++
- Algorithms

Advertisement

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;

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.

No longer taking questions.

No longer taking questions.**Education/Credentials**

No longer taking questions.