CODEWITHSUNDEEP
performancetimeasymptotic-complexity
krnactry
krnactry

Reputation: 57

why is this running time o(n)? Using two queues to implement stack pop

For pop operation : 
If Q1 is empty , an underflow has occurred , throw an error
Else , we copy all but the last element of Q1 to Q2 , we return the last element copied .         
We then copy back the elements from Q2 to Q1.

I thought this would be constant growth rate because if it has one item then, that would always result in constant time?

Upvotes: 0

Views: 39

Answers (2)

Florin Balint
Florin Balint

Reputation: 26

Copying the elements by itself needs O(n) running time complexity. If you are familiar with what the asymptotic notation means the you know it is refers to number of "basic" operations. You have to copy the memory one by one element at a time. Even if you copy blocks of memory that would still be at most a constant amount, lets call it k. Making N/k operations means that you still have a O(n) complexity. Now you can see that the first step takes O(n) , the second one O(1) (return and assign?) and the last one takes O(n) again and after summing them you get a total of O(n).

Upvotes: 1

Eric J.
Eric J.

Reputation: 150138

we copy all but the last element of Q1 to Q2

The time to copy the elements depends on how many elements there are. O(n).

We then copy back the elements from Q2 to Q1

Also an O(n) operation. Two O(n) operations are still O(n).

because if it has one item then, that would always result in constant time?

Sure if you always have one item, it will run in constant time. Big-O notation is concerned with the behavior of the system when you have n items, and n is large.

Upvotes: 1

Related Questions