3
$\begingroup$

I'm trying to figure out amortised analysis of this loop and I can't figure out how to prove that complexity is $O(n \log n)$.

Operation OP(S,X[i]) has complexity O(log|S|) and operations push and pop has constant complexity O(1).

S <- Emptystack
for i=1 to n do
    while (S!=0) and OP(S,X[i]) do
        pop(S)
    od
    push(S,X[i])
od

I would like to proove it using potential function. It would be simple if there were just pop(S) and push(s):

Pot.function represents number of items in stack

C^ PUSH = 1 + |S|+1 - |S| = 2

C^ POP = 1 + |S|-1 - |S| = 0

So the complexity would be linear (O(2n)) = O(n). But I don't know how to compute amortized complexity of OP.

$\endgroup$
2
$\begingroup$

We can divide the running time into several parts:

  • Pushes.
  • Pops.
  • The first OP performed at every round.
  • Subsequent OPs performed at every round.

Note that every OP costs $O(\log n)$, that there are at most $n$ pops, and that each "subsequent OP" follows a pop. We conclude that the total running time of pushes and pops is $O(n)$, the total running time of first OPs is $O(n\log n)$ (since there are $n$ rounds), and the total running time of subsequent OPs is $O(n\log n)$ (since there are at most $n$ pops). In total, the running time is $O(n\log n)$.

If you want to use the potential method, try to use a potential of the form $|S| + \log(|S|!)$.

$\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.