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

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$

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.

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

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

@lambda  how to verify that the answer is option C?

yes i get lifetime of one  element =Y but how to verify with option C?

---

By putting the value of $n=1,$

Now the four option will looked as follows:

(A) $n(X+Y)=X+Y$

(B)$3Y+2X$

(C)$n(X+Y)-X=Y$

(D) $Y+2X$

So the option C

---

best approach to solve this question within minutes without derivation

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

Answer 5

Correct answer is Option C

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

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

Answer 6

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 7

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.