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

Correct answer is Option C

Please go through below image, there I have solved using Option elimination.

https://photos.app.goo.gl/2bZ0QISbgnpQxCGg2

Answer 2

The option for this question is C.

Answer 3

Lets solve it for 3 elements and verify the options to find the correct ans.
for 3rd element pushed on to stack Life time is: Y
for 2nd element pushed on to stack Life time is: 2X+2Y+Y
for 1st element pushed on to stack Life time is: 4X+4Y+Y
therefore average life time for 3 elements: (6X+9Y)/3=2X+3Y

option (c) putting n=3 gives 2x+3y therefore (c) is the correct ans.

Answer 4

All those calculations might take a while, so I tried to look at this from another quicker perspective.

Let's say n=1 and the average stack-life for m elements (in this case only 1) will then be just Y. So definitely, Y>X. We can strike out options a and d totally.

So how do we pick in between b and c? Now let's assume n is infinitely large. There would be no way it would be option b since it's too less and therefore, option c makes more sense.

Also, if we substitute n=1 into option c, we get Y which is correct. I guess this kind of perspective can be taken into consideration if you are not sure of the answer with the technique used earlier. Hope this helps.