GATE CSE 2003 | Question: 64

Question

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

• A. $n(X+Y)$
• B. $3Y+2X$
• C. $n(X+Y)-X$
• D. $Y+2X$

Comments

 $\fbox{Ans: C}$

---

$Stack\ lifetime\ of\ m:$

$After\ push\ 'm'$

$\fbox{Stack lifetime}$

$Before\ pop\ 'm'$

---

$Let\ n=3$

	////////	$Y$
$X$	$C$	$X$
$Y$	///////	$Y$
$X$	$B$	$X$
$Y$	//////	$Y$
$X$	$A$	$X$

$A=Y+X+Y+X+Y+X+Y+X+Y=>4X+5Y$

$B=Y+X+Y+X+Y=>2X+3Y$

$C=Y=>1Y$

$Avg: \dfrac{6X+9Y}{3}=2X+3Y$

Option $A$ and $D$ eliminated 

$Let\ n=2$

	///////	$Y$
$X$	$B$	$X$
$Y$	//////	$Y$
$X$	$A$	$X$

$A=Y+X+Y+X+Y=>2X+3Y$

$B=Y=>1Y$

$Avg: \dfrac{2X+4Y}{2}=X+2Y$

Option $B$ eliminated 

---

Take some simple value lets say

X=2

Y=3

n=1(no of element)

according the definition

define the stack-life of mm as the time elapsed from the end of Push(m)Push(m) to the start of the pop operation that removes mm from S

so life of the element which is in top is only Y

so for 1 element answer is 3 according to our assumption 

let’s put N,X and Y in option 

1. n(X+Y) = 1(2+3) = 5 != 3 not correct
2. 3Y+2X = 3*3 +2*2 = 13 != 3 not correct
3. n(X+Y)-X = 1(3+2)-2 = 3 == 3 so this is the answer
4. Y+2X = 3+4 = 7 !=3 

---

diff=difference b/w 'start of pop time' and 'end of push time'=stack life
In the enclosed blue box i  simplified the "difference" i.e stack life of each element before computing their average.
 

Answer 1

Let insert elements 1,2,3 into stack and pop it

1x.  ( Y)   2x.  ( Y)   3x. ( Y)    3x. (Y  )    2x.  ( Y )    1x

Here x represent time required pop or push operation....

Y represent time elapsed between two operations...

Life time of 1 = 5y + 4x

Life time of 2 = 3y + 2x

Life time of 3 = y + Ox

Avg = total time / total values

       = (9y + 6x)/3

        = 3y +2x

For instead of 3 values if we do for 4 values

Avg will be= 4y + 3x

So it is nothing but...  n(x+y)-x

Answer 2

Consider set A [1...m...n] be the elements.

Case 1: 'm' is the terminal element : Y(wait) $\Rightarrow$ Y
Case 2: 'm' is followed by one element only :  Y(wait) + X(push:m+1) + Y(wait) + X(pop:m+1) + Y(wait) $\Rightarrow$ 3Y + 2X
Case 3: 'm' is followed by two elements only :
Y(wait) + X(push:m+1) + Y(wait) + X(push:m+2) + Y(wait) + X(pop:m+2) + Y(wait) + X(pop:m+1) + Y(wait) $\Rightarrow$ 5Y + 4X

Hence the answer should be N(X+Y)-X.

Answer 3

Let there is only one element. So only one element is to be pushed and pop.

| 1 |     |     |

let this be the stack so time elapsed between pushed and poped is Y.

so lifetime = Y when n=1

put n=1 in answer see that in option (c) 1(X+Y)-x=y is matching so c is the answer . no other options are matching.

Answer 4

I think it can be solved easily by substituting from options....