I have the following simple Java code:

while(i>1)
{
    i = i/2;
}

I am having trouble understanding how to make a mathemtical computation to know that the time complexity of it is O(logn). How can I prove that in a simple way?

CodePudding user response：

How many times do you need to divide i by 2 until it become 1?

i / 2ⁿ = 1

i = 2ⁿ

Knowing that log₂(a) = b implies that 2^b = a, we get

n = log₂(i)

Hence the complexity of the loop is O(log₂(i)) = O(log(i)).

CodePudding user response：

i=10

6/2=5 -> 5/2=2 -> 2/2=1

each cycle exclude half O(logn) means O(log₂n)

CodePudding user response：

Assuming i is an int, the binary representation of i loses one bit off the right in each loop iteration until it's 0, suggesting the total number of iterations is the number of bits needed to represent i. The number of bits needed to represent i is ceil(lg(i)) 1, which you can show is Theta(log n) using the change of base log rule, and the definition of big-Theta.