edited by
30,718 views
89 votes
89 votes

Let S be a stack of size $n \geq1$. 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 operations 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 \geq1$, 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$
edited by

12 Answers

Best answer
72 votes
72 votes
Let us represent stack-life of $i^{th}$ element as $S(i)$. The $i^{th}$ element will be in stack till $(n-i)$ elements are pushed and popped. Plus one more $Y$ for the time interval between the push of $i^{th }$ element and the $i+1^{th}$ element. So,

$S(i) = Y + 2.(n-i)(Y+X) \\= Y + 2.(n-i)Z \\= Y + 2nZ -2iZ$

where $Z = Y+X$

average stack-life will, $A = \Sigma \frac{S(i)}{n}$

$nA = nY + 2.n.n.Z -2.Z.\Sigma i$

$nA = nY + 2.n.n.Z - 2.Z \frac{(n(n+1))}{2}$

$nA = nY + 2.n.n.Z - Z(n.n) - n.Z$

$A = Y + 2.n.Z - (n+1).Z$

$A = Y + (n-1).Z \\= Y +(n-1)(X+Y) \\= n(X+Y) - X$

Correct Answer: $C$
edited by
118 votes
118 votes

Lifetime of m : End Of Push to Start of Pop

  • n - PUSH  will take $X$ seconds each
  • n - POP  will take $X$ seconds each
  •  Time Between  two PUSH  or two POP or one PUSH one POP is $Y$ second

Consider an example with stack contails 3 elemets as shown in Image below

Option C

edited by
46 votes
46 votes

For quick answer:

consider $n=1,$

We pushed only element with value $1$ into the stack.

Time after push is $X$

After a break of time $Y$, we can pop the element from the stack.

Time before pop is $X+Y$

Lifetime of element $1=(X+Y)-X=Y$

Now we can easily verify that the answer is option $C$

9 votes
9 votes

Here is my approach:

Stack lifetime of nth element -> Y
For (n-1)th -> 2X+2Y + stack lifetime of nth element = 2X + 3Y
For (n-2)th -> 2X+2Y + stack lifetime of (n-1)th element = 4X + 5Y
..
..
For 1st -> 2(n-1)X + (2n-1)Y

Sum of all life spans= (Σ 2(n-1)X) + (Σ (2n-1)Y) for n = 1 to n

Calculate sum by the above summation from 1 to n, You will get:

Sum = n(n(X+Y)-X)
Therefore Average = Sum/n = n(X+Y)-X .  Hence Option (c)
source @ http://stackoverflow.com/questions/24464942/stack-life-span
reshown by
Answer:

Related questions

79 votes
79 votes
10 answers
2
Disha asked Sep 19, 2014
31,713 views
In a min-heap with $n$ elements with the smallest element at the root, the $7^{th}$ smallest element can be found in time$\Theta (n \log n)$$\Theta (n)$$\Theta(\log n)$$\...
81 votes
81 votes
6 answers
4
Kathleen asked Sep 16, 2014
22,317 views
Let $T(n)$ be the number of different binary search trees on $n$ distinct elements.Then $T(n) = \sum_{k=1}^{n} T(k-1)T(x)$, where $x$ is $n-k+1$$n-k$$n-k-1$$n-k-2$