CODEWITHSUNDEEP
while-looptime-complexity
Cdesai
Cdesai

Reputation: 1

Time complexity for while loop

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?

Upvotes: 0

Views: 3621

Answers (2)

kamoroso94
kamoroso94

Reputation: 1735

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.

Upvotes: 1

Brian
Brian

Reputation: 15740

The time complexity would be O(log(n)) because x is increasing exponentially.

Upvotes: 3

Related Questions