The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+29 votes
3.6k 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 (69k points)
edited by | 3.6k views

5 Answers

+30 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 Veteran (14.1k points)
selected by

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.
+32 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 Veteran (24.4k 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.
+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 Boss (5.9k points)
reshown by
+4 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 (719 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$

(B)$3Y+2X$

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

(D) $Y+2X$

So the option C

+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 Junior (979 points)


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

33,687 questions
40,230 answers
114,269 comments
38,800 users