What would be the time complexity of this while loop:

Question

    int i = n;
    while (i > 0){
    cot += 1
    i = i/2;
        }
    }
}

can someone please explain this with steps for each line? im having an extremely difficult time witht his. I know the answer is O(log n) but I dont know how to get there

Answer 1

The line cot += 1 is not used anywhere so I will ignore it.

In each loop you divide the initial n by 2 and do that until it reaches 0. So for instance, let's say you have n=32. You divide it by 2 until it reaches 0. So you have the sequence i=32 -> 16 -> 8 -> 4 -> 2 -> 0.

So to figure out how many steps it will take you solve the equation N^k = n, where N is the number you're dividing with, k is your number of steps and n is the initial number. So for our example above where N=2, n=32 we solve for 2^k=32. The solution = log2(32) = 5.

The precise complexity would be log2(n), but you can rearrange this in a way that log(2) becomes a constant and you can ignore it (change of base formula).