CODEWITHSUNDEEP
algorithmdata-structurestime-complexitybig-otheory
Rayyan Khan
Rayyan Khan

Reputation: 23

If stack operations are constant time O(1), what is the time complexity of this algorithm?

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

Upvotes: 2

Views: 1303

Answers (2)

Ashwin Ganesan
Ashwin Ganesan

Reputation: 331

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

Upvotes: 0

Abhinav Mathur
Abhinav Mathur

Reputation: 8111

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).

Upvotes: 5

Related Questions