What is the time complexity of
x = 1
while( x < SomeValue )
{
x *= 2;
}
I believe it is O(N), as the loop will continue for a fixed number of iteration. Is my assumption correct?
-
I don't mind being wrong, but just that if I am wrong then what is the right answer.Cdesai– Cdesai2016-08-10 21:39:51 +00:00Commented Aug 10, 2016 at 21:39
-
If it's a fixed number of iterations, how many is it?David Schwartz– David Schwartz2016-08-10 22:08:16 +00:00Commented Aug 10, 2016 at 22:08
Add a comment
|
2 Answers
The time complexity would be O(log(n)) because x is increasing exponentially.
3 Comments
cybersam
Unless
SomeValue <= 1, in which case complexity is O(1).
Brian
@cybersam You could apply that argument to any big O notation. If you specify the value of
n, you can always solve it to a constant, thereby turning it into O(1).cybersam
If SomeValue > 1, then the complexity is
O(log(SomeValue)), not O(1).The loop will execute in O(log n) time. Hopefully the math makes the reasoning more clear. Each iteration is constant time. To find the number of iterations relative to SomeValue, which we'll call t, you can see that after the nth iteration, x will have the value 2ⁿ. The loop ends once x≥t. So to find the number of iterations needed to meet or exceed t, plug in 2ⁿ for x and solve for t. You get t=log₂(n). Hence, O(log n) time.
