GATE CS 2003 Q64 — Arrays, Stacks and Queues

To find the average stack-life, we analyze the timeline of the $2n$ operations: $Push(1), \dots, Push(n)$ followed by $Pop(n), \dots, Pop(1)$.

Each operation takes $X$ seconds, and $Y$ seconds elapse between consecutive operations. Thus, the $i$-th operation in the sequence starts at $t = (i-1)(X+Y)$ and ends at $t = iX + (i-1)Y$.

For any element $m \in \{1, 2, \dots, n\}$:

• It is pushed by the $m$-th operation, which ends at:
  $$t_{\text{push\_end}}(m) = mX + (m-1)Y$$
• It is popped by the $(2n - m + 1)$-th operation, which starts at:
  $$t_{\text{pop\_start}}(m) = (2n - m)(X+Y)$$

The stack-life $L(m)$ of element $m$ is the duration between these two events:

Letting $k = n-m$, as $m$ ranges from $1$ to $n$, $k$ ranges from $0$ to $n-1$. The average stack-life is:

Using the identity $\sum_{k=0}^{n-1} k = \frac{n(n-1)}{2}$: