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 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$

Comments

s(i)=Y+2(n-i)(Y+X)
In above equation, why we are taking one extra Y?
 

---

Explained now..

---

Sir, why we are considering time interval between the push of ith element and the i+1th element only ?

---

Lets take n value is 4, then after pushing the 4th item there be a Y elapse time before the pop operation begins. And this Y value will be added to the elapse time every item reside in the stack.

---

@Utsav09

it is mentioned in the question :)

---

Easiest method for solution under 1 min:-

Take $n=1$, operations: $Push(X) + Wait (Y) + Pop (X)$

“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. “

Therefore, stack life for $1$ element: $Y$

average must be: $Y/1 = Y$

Now, only in option C)  $n(X+Y)-X = 1(X+Y)-X = Y$

Hence Option C is the answer.

---

@Abhrajyoti00 this is good for exams, but not during preparation. 

We should definitely know how to solve by putting values in options but we should not jump to the next question after doing so.

---

Yes, @Sachin Mittal 1 Sir, I agree. Moreover, this question actually builds the concept to solve such qs. The soln. I proposed above was only for exam purpose.

---

We can also solve this using recurrence relation. Let T(n) be the stack life of a particular element n. Then T(n)=T(n+1) + 2X + 2Y. Let me explain how this eq is coming…

T(n+1) is the time span(ie the time it spends in the stack) of (n+1)^th element. Time span of n ^th element will include this time plus the additional time it spends in stack. Now coming to the additional time.

→  After inserting n ^th element there is a Y sec of elapse + X sec consumed in the insertion of (n+1)^th element so (X+Y) is the additional time spend by n ^th element. Now at the time of popping elements firstly (n+1)^th element is popped then n ^th element is popped. So X sec are consumed while popping (n+1)^th element which is not counted in the time span of  (n+1) ^th element (ie T(n+1) ). Plus Y sec are consumed before start of the pop operation of n ^th element. So n ^th element spends this (X+Y) additional time in stack. So total additional time=  (X+Y) +  (X+Y)= 2X+2Y.

--Now suppose total of n elements are inserted. We can easily find out the time span of n ^th element. 

Suppose at t=q push operation of n ^th element starts. So at t=q+X it is inside the stack. At t=q+X+Y pop operation of n ^th element starts. So time spended by n ^th element T(n)= (q+X+Y) – (q+X)= Y.

By recurrence relation we can find out the time span of (n-1) ^th element.

Base case: T(n)=Y.

T(n-1)=T(n)+ 2X + 2Y= Y + 2X + 2Y= 2X+3Y.

T(n-2)=T(n-1)+ 2X + 2Y=(2X+3Y)+2X + 2Y=4X+5Y.

We can observe that it is forming AP with d= 2X + 2Y.

So avg stack life = ( T(n)+T(n-1)+T(n-2)…..T(1) ) / n.

We can find the summation of AP by the formula n/2[2a + (n − 1) × d] where a is the first term ie a= Y 

Avg stack life = ( n/2[2Y + (n − 1) ×(2X + 2Y) ] ) / n

Avg stack life = 1/2[2Y + (n − 1) ×(2X + 2Y) ] = Y + (n-1)×(X+Y) = n(X+Y) – X

So the answer would be option C :)

Answer 2

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

Comments

Avg lifetime = sum of life time of all elements/no of elements

so avg lifetime in your example = 9x + 6y/3  (n = 3)

so it give 3x + 2y which can be easily observed by putting n=3 in option C.

---

@parthbkgadoya, avg lifetime in above example should be 6x+9y/3= 2x+3y

---

Why pop2 time no included in lifetime of 2.

@pC

Pls explain.

---

@parthbkgadoya when we put n=3, it should be 2X+3Y not 3X+2Y.

Answer 3

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$

Comments

Never Commented Here, But Wow Dude This Approach Deserves It, Thank You

---

can you please explane why we minus last extra X

---

Great approach!

Answer 4

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