I have been learning DSA, but calculating time complexity is a little difficult

I understand the logic of O(n^2) or O(n)

but what will be the time complexity of and how?:

while(n%2 == 0) {
    n/=2;
}

It will be O(n/2)? not sure

CodePudding user response：

There's obviously a lower bound of O(1) for when n is initially odd. But that's not the complete answer.

There is an upper bound.

Here's a hint. How many loop iterations of executing n = n/2 for the following initial values of n:

n = 1   =>  0 iteration
n = 2   =>  1 iterations
n = 4   =>  ?
n = 8   =>  ?
n = 16  =>  ?
n = 32  =>  ?
n = 64  =>  ?
n = 128 =>  ?

Now what math function, can f(n) be implemented with that can predict the count of iterations given an initial value of n? This will give you an upper bound for the runtime complexity.

CodePudding user response：

You can test it practically to see how much iterations loop will have depending of n

int main()
{
   int n = 2048;
   int count = 0;
   
   while(n%2 == 0) {
        n/=2;
          count;
    }
    std::cout << count;
    return 0;
}

So, when n = 1024, count = 10 when n = 2048, count = 11

2^(iteration count) = N;

So, complexity would be O(Log 2 (N))

CodePudding user response：

To evaluate the time complexity of your code, always test for the worst case possible.

For instance, if you try n = 9, the while won't even enter. So the worst case possible is when you divide n more times, and that case would be n = 2^k.

Now, it's easy to see that you need k operations for the while to finish.

If n = 2^k, then k = log₂(n), hence the complexity is O(log₂(n)).