Stack life

Computer Science Level 3

Let $S$ be a stack of size greater than $1$ . Starting from an empty stack, suppose we push the first $n$ natural numbers in sequence and then perform $n$ pop operations. For $1\leq x\leq n$ the stack life of $x$ is defined as the time taken from the end of push(x) to the start of the pop operation that removes $x$ from $S$ . What of the following is the correct representation for the average stack life of $x$ ?

Details and Assumptions

$k$ is the number of seconds required to pop and push an item
$l$ is the number of seconds elapsed between each successive operations.

n(k+l)

2n(k+l)

n(k+l)-k

n(k+2l)

1 solution

You Kad
Jul 29, 2016

Stack Life Drawing The stack life of $x = 1$ is equal to $2(n-1)(k + l) + l = (2n-1)(k+l) - k$ (see the drawing).

Likewise, the stack life of $i \in [1, n] \cap \mathbb{N}$ is equal to $2(n-i)(k + l) + l = (2n-2i + 1)(k+l) - k$

Therefore, the average stack life is :

$\displaystyle \dfrac{1}{n} \sum\limits_{i = 1}^n \Big( (2n + 1)(k+l) - k - 2i(k+l) \Big) = (2n + 1)(k+l) - k - \frac{1}{n}\frac{2(k+l)n(n+1)}{2} = n(k+l) - k$

Stack life

1 solution

0 pending reports