The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+38 votes
5.2k views

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 (59.7k points)
edited by | 5.2k views

7 Answers

+39 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$
answered by Boss (13.5k points)
edited by
0

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

0
Explained now..
0

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

+1
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.
+43 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 (22.5k points)
edited by
+2
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.
0
@parthbkgadoya, avg lifetime in above example should be 6x+9y/3= 2x+3y
+10 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 Junior (901 points)
0
@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?
+3

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

+5 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 @ http://stackoverflow.com/questions/24464942/stack-life-span
answered by Loyal (6.1k points)
reshown by
+4 votes

Correct answer is Option C

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

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

answered by Active (1.6k 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 (447 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 (39 points)
Answer:

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

44,297 questions
49,785 answers
164,368 comments
65,857 users