Let S be a stack of size n ≥ 1. Starting with the empty stack, suppose we push…
2003
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
- A.
n (X + Y)
- B.
3Y + 2X
- C.
n (X + Y) - X
- D.
Y + 2X
Attempted by 320 students.
Show answer & explanation
Correct answer: C
Solution: Derivation of the average stack-life.
End time of Push(m): mX + (m-1)Y
Start time of the first pop (after all pushes): nX + nY
Element m is popped as the (n-m+1)-th pop, so the start time of the pop that removes m is nX + nY + (n-m)(X+Y).
Therefore the stack-life of element m equals (start of its pop) minus (end of its push):
Stack-life(m) = [nX + nY + (n-m)(X+Y)] - [mX + (m-1)Y]
Simplifying gives:
Stack-life(m) = 2(n-m)(X+Y) + Y.
Average stack-life over all n elements:
Compute sum of (n-m) for m = 1..n: ∑_{m=1}^n (n-m) = 0+1+…+(n-1) = n(n-1)/2
Sum of stack-life over m = 1..n: ∑ [2(n-m)(X+Y) + Y] = 2(X+Y) * n(n-1)/2 + nY = (X+Y)n(n-1) + nY
Divide by n to get the average:
Average = (1/n)[(X+Y)n(n-1) + nY] = (X+Y)(n-1) + Y = n(X+Y) - X
Final answer: n(X+Y) - X