CODEWITHSUNDEEP
algorithmcomplexity-theory
veronik
veronik

Reputation: 177

Amortized analysis of an ordered stack

I was working through a tutorial sheet I found online and came across a question I couldn't figure out how to solve.

http://www.bowdoin.edu/~ltoma/teaching/cs231/fall08/Problems/amortized.pdf

An ordered stack S is a stack where the elements appear in increasing order. It supports the following operations:

Init(S): Create an empty ordered stack.

Pop(S): Delete and return the top element from the ordered stack.

Push(S, x): Insert x at top of the ordered stack and re-establish the increasing order by repeatedly removing the element immediately below x until x is the largest element on the stack.

Destroy(S): Delete all elements on the ordered stack.

Argue that the amortized running time of all operations is O(1). Can anyone help?

Upvotes: 1

Views: 2669

Answers (2)

Pooya Afshari
Pooya Afshari

Reputation: 39

There are several operations mentioned for the Ordered Stack which are listed below:

  1. Init(S): which we know it will take O(1)

  2. Destroy(S): also we know it will take O(1)

Lets do Amortized Analysis( Amortised cost(Ci) = Actual cost(ci ) + change in potential )

  1. Pop(S): we know the ci of 'pop' will be 'O(1)', so we create a potential function 'Phi'.

Ci = ci +Φ(Di-1)-Φ(Di) = 1+n-1-(n) = 0

-> O(1)

  1. Push(S,x):

  • If x is greater than the top, we know the time ci is O(1) as equal to push. ( we can prove this as we did for push in amortized analysis, instead this time for push ).

  • If x is less than the top we should do 'MultiPop' and a 'Push' operation so let's do Amortised Analysis again:( Let's say ci is k+1 as we pop k first items of the stack and push one item on top )

Ci = ci +Φ(Dj) - Φ(Di) = (k+1) + (S-k+1) - S

-> Ci = 2

-> O(1)

( I just wrote what I thought about the solution to this problem so if anything is not correct tell me in the comments and I will check that. )

Upvotes: 0

Haris
Haris

Reputation: 12272

i think what you can do is,

firstly prove that init(s), pop(S) and destroy() really actually takes O(1) time ( and they really do.)

then for the push(S, x) function that is asymtotically increasing the complexity to O(n) argue that the push() will start with O(1) time and continue to give the same complexity until unless a number smaller than the top of the stack in pushed. the probability of this happening can be calculated to support your argument.

(do comment if something is not correct)

Upvotes: 1

Related Questions