1
$\begingroup$

Assume that we have a data type $stack$ which has two operation $push$ and $pop$, both operations' time complexity is $O(1)$ in worst case. The $stack$ also has a property $size$ indicate how many elements are in the $stack$, and can be accessed in constant time.

I want to emulate a $queue$ by using two stacks $queue = (stack_{push}, stack_{pop})$ with two operations $insert$ and $remove$

$insert(queue, e)$ is implemented as:

insert(queue, e) {
    push(stack_push, e)
}

$remove(queue)$ is implemented as:

remove(queue) {
    if (stack_pop.size > 0) {
        pop(stack_pop)
    } else {
        while(stack_push.size > 0) {
            push(stack_pop, pop(stack_push))
        }
        pop(stack_pop)
    }
}

It is obviously that $insert$ takes constant time and $remove$ takes $O(n)$ time in worst case. (where n is the size of the queue).

Now considering an sequence of queue operation with length $n$ (pop an empty stack is allowed), I want to get the amortized time complexity of this queue structure. My guess is that the amortized time complexity is $O(1)$, since it seems that the worst case of the sequence is first $insert$ n-1 elements then $remove$, so the total cost is $O(n)$ then the amortized time is $O(n)/n = O(1)$. However I cannot figure out how to prove it.

My question is that is the amortized time complexity of the queue's operation really $O(1)$ and how to prove it?

$\endgroup$
  • $\begingroup$ yes, the amortized complexity is still O(1) because the worst case always occurs when the stack_pop is empty. $\endgroup$ – Navjot Waraich Mar 12 at 9:07
1
$\begingroup$

In the remove operation, every iteration of the while loop pops an element from stack_push, and this dominates the running time of remove. We can charge each such iteration to the insert operation which pushed the very same element to stack_push. This way we deduce that the amortized running time of both operations is $O(1)$.

You can formalize the above argument in various ways. As an example, if you perform $A$ insert operations and $B$ remove operations, then the argument above shows that you push at most $2A$ elements and pop at most $A+B$ elements. Hence the total running time is $O(A+B) = A \cdot O(1) + B \cdot O(1)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.