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)
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)
Jump to PostActually I think that loop is linear, so it should be O(n).
Jump to PostIt 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 …
o(square root of n )
I agree
It's O(square root of n), not o(square root of n).
Actually I think that loop is linear, so it should be O(n).
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.
Ah yes you are correct. The loop is not linear.
what is the time complexity of algoritham?
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.