The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+40 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$

asked in DS by Veteran (52k points)
edited by | 6.1k views

7 Answers

+42 votes
Best answer
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$
answered by Boss (13.2k points)
edited by

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.
+49 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

answered by Boss (21.1k points)
edited by
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
+16 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$

answered by Active (1k points)
@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$



(D) $Y+2X$

So the option C

best approach to solve this question within minutes without derivation
+6 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 @
answered by Active (5k points)
reshown by
+4 votes

Correct answer is Option C

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

answered by Active (2k points)
0 votes
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.
answered by Junior (663 points)
0 votes
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.
answered by (219 points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
49,535 questions
54,120 answers
71,034 users