How to calculate average stack-life of an element in a stack?


#1

Let S be a stack of size n >= 1. Starting with the empty stack, suppose we push the first n natural numbers in sequence, and then perform n pop operations. Assume that Push and Pop operation take X seconds each, and Y seconds elapse between the end of one such stack operation and the start of the next operation. For m >= 1, define the stack-life of m as the time elapsed from the end of Push(m) to the start of the pop operation that removes m from S. The average stack-life of an element of this stack is

  1. n(X+ Y)
  2. 3Y + 2X
  3. n(X + Y)-X
  4. Y + 2X

#2

let us represent stack-life of ith ith element as S(i). The ithith element will be in stack till (n−i)(n−i) elements are pushed and popped. Plus one more YY for the time interval between the push of ithith element and the i+1thi+1th element. So,

S(i)=Y+2.(n−i)(Y+X)=Y+2.(n−i)Z=Y+2nZ−2iZS(i)=Y+2.(n−i)(Y+X)=Y+2.(n−i)Z=Y+2nZ−2iZ

where Z=Y+XZ=Y+X

average stack-life will, A=ΣS(i)nA=ΣS(i)n

nA=nY+2.n.n.Z−2.Z.ΣinA=nY+2.n.n.Z−2.Z.Σi

nA=nY+2.n.n.Z−2.Z(n(n+1))2nA=nY+2.n.n.Z−2.Z(n(n+1))2

nA=nY+2.n.n.Z−Z(n.n)−n.ZnA=nY+2.n.n.Z−Z(n.n)−n.Z

A=Y+2.n.Z−(n+1).ZA=Y+2.n.Z−(n+1).Z

A=Y+(n−1).Z=Y+(n−1)(X+Y)=n(X+Y)−XA=Y+(n−1).Z=Y+(n−1)(X+Y)
=n(X+Y)−X
Hence option C


#3

You Can refer to the image above.