BinaryConversion: We are inputting a positive integer n with the output being a binary representation of n on a stack.

What would the time complexity here be? I'm thinking it's O(n) as the while loop halves every time, meaning the iterations for a set of inputs size 'n' decrease to n/2, n/4, n/8 etc.

Applying sum of geometric series whereby n = a and r = 1/2, we get 2n.

Any help appreciated ! I'm still a noob.

create empty stack S
while n > 0 do
    push (n mod 2) onto S
    n = floor(n / 2)
end while
return S

CodePudding user response：

If the loop was

while n>0:
    for i in range n:
        # some action
    n = n/2

Then the complexity would have been O(n n/2 n/4 ... 1) ~ O(n), and your answer would have been correct.

while n > 0 do
    # some action
    n = n / 2

Here however, the complexity will should be the number of times the outer loop runs, since the amount of work done in each iteration is O(1). So the answer will be O(log(n)) (since n is getting halved each time).

CodePudding user response：

The number of iterations is the number of times you have to divide n by 2 to get 0, which is O(log n).