time complexity of algorithm

[mithila]

Please do let me know the time complexity of algorithm

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

i think the O(squareroot of n)

[R_brahmankar]

o(square root of n )

[Jim Larkin]

I agree

[sarehu]

It's O(square root of n), not o(square root of n).

[darkagn]

Actually I think that loop is linear, so it should be O(n).

[sarehu]

It is O(n), but it's also O(n^2) and O(2^n), because the running time grows slower than all of those functions. You'll notice that the value of s grows quadratically, that is, on the k'th iteration of the loop, s will equal k*k. So it takes sqrt(n) iterations (give or take one) until s is not less than n. O(sqrt(n)) is the tightest upper bound you can use to describe how the procedure's running time grows as n grows.

[darkagn]

Ah yes you are correct. The loop is not linear.

[umesh sevra]

what is the time complexity of algoritham?