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


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


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,


where Z=Y+XZ=Y+X

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





Hence option C


You Can refer to the image above.