The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+11 votes

A program consists of two modules executed sequentially. Let $f_1(t)$ and $f_2(t)$ respectively denote the probability density functions of time taken to execute the two modules. The probability density function of the overall time taken to execute the program is given by 

  1. $f_1(t)+f_2(t)$

  2. $\int_0^t f_1(x)f_2(x)dx$

  3. $\int_0^t f_1(x)f_2(t-x)dx$

  4. $\max\{f_1(t),f_2(t)\}$

asked in Probability by Veteran (69k points) | 1.6k views

3 Answers

+15 votes
Best answer
We assume the total time to be ‘t’ units and f1 executes for ‘x’ units.

Since, f1(t) and f2(t) are executed sequentially.
So, f2 is executed for ‘t – x’ units.

We apply convolution on the sum of two independent random variables to get probability density function of the overall time taken to execute the program.

f1(t) * f2(t – x)
answered by Loyal (4.1k points)
selected by
+6 votes

Solution: C

Since the two modules execute sequentially. The total runtime of the program is the sum of runtime of the the two modules. Probability mass function of sum of two random variable is given by the convolution in the option C.


answered by Active (1.4k points)
+6 votes

$f_k(t)$ denote the probability density function of time taken to execute module (Here k = 1, 2). Means probability that module k will take 5 unit of time is given by $f_k(5)$.

Now let us assume total execution time is  4 unit then it's probability will be given by  -->

$f_1(0)*f_2(4)$ + $f_1(1)*f_2(3)$ + $f_1(2)*f_2(2)$ + $f_1(3)*f_2(1)$ + $f_1(4)*f_2(0)$

(means for example if first module takes 3 unit then another module should take 1 unit of time(and both probabilities are independent because module execution is sequential) so it's probability is $f_1(3)*f_2(1)$  ).

If entire program execution time is t unit then we can write general formula for it's probability as

  $f_{total}(t) = $$\int_{0}^{t}$ $ f_1(x)*f_2(t-x)$dx$ $

which is also telling probability density at point 't' or $f_{total}(t)$ is our desired probability density function for entire program execution.


Answer is (C) part.

answered by Veteran (14.7k points)
edited by

what will be the answer if the program modules execution is parallel not sequential???

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,646 questions
40,193 answers
38,665 users