-1
p = 0
for(i=1;p<=n;i++){
 p = p+i;
}

How can I analyze the time complexity of this loop? I read that it's O(n^(1/2)). But How?

tusharK3411
  • 85
  • 1
  • 3
  • Review this article: https://stackoverflow.com/questions/11032015/how-to-find-time-complexity-of-an-algorithm – Nisarg Sep 04 '18 at 20:46
  • Where did you read that it's O(n^(1/2))? – Yogurt Sep 04 '18 at 21:46
  • 2
    Possible duplicate of [How to find time complexity of an algorithm](https://stackoverflow.com/questions/11032015/how-to-find-time-complexity-of-an-algorithm) – Adrian W Sep 04 '18 at 21:58

2 Answers2

2

How is p increasing? First we add 1, then 2, then 3... then k.

So at step k, p = 1 + 2 + 3 + ... + k. The formula for this is k * (k + 1) / 2. Now, how many steps are needed to reach n?

Let´s try replacing k for sqrt(2n). We have from the formula, sqrt(2n) * (sqrt(2n) + 1) / 2. This is equal to 2n + sqrt(2n) / 2. This is equal to n + some constant. So in sqrt(2n) iterations, we have already reached p > n. This gives us an upper bound of O(sqrt(2n)) which is the same as O(sqrt(n)).

juvian
  • 15,875
  • 2
  • 37
  • 38
0
p = 0
for(i=1;p<=n;i++){
 p = p+i;
}

For every iteration you are adding a 1 no. higher than previous

step 1 : p = p + 1;
step 2 : p = p + 2;
step 3 : p = p + 3;
step 4 : p = p + 4;
.....
.....
step m : p = p + m;

Your condition is compare the p with n

p<=n

Sum of values you are adding in p will be like

1+2+3+.....+m <= n

In Maths, Equation to solve above Sum will be like

(m * (m + 1))/2 <= n

So, the final complexity reaches to

ManishM
  • 583
  • 5
  • 7