1
$\begingroup$

Suppose we have two discrete random variables and we want perform maximum operation to obtain the max PDF.

We know that max of two independent random variables is: if Z = max(X,Y)

pr(Z = k) = pr(X = k) pr(Y < k) + pr(X < k) pr(Y = k) + pr(X = k) pr(Y=k)

Or to visulize: maximum

My question how this operation has O(nm) timing complexity where n and m are the sample size of X and Y receptively or O(n^2) when both has n samples.

It should not be O(n)? for instance the example i've shown in picture there is 3 multiplication and 4 sums for each max sample and if we increase the number of X and Y samples to 8 the multiplications number still the same and the sums doubles so it's linear.

Could you please correct me if i'm wrong?

Improve this question
$\endgroup$
4
  • $\begingroup$ Your calculation assumes that both the PDF and CDF are available and can be evaluated in $O(1)$ time. This suggests that computational complexity for computing $Z$ is not a well-defined quantity, because it ultimately depends on the form in which the distributions of $X$ and $Y$ have been presented to you. Could you tell us specifically what that form is? $\endgroup$
    – whuber ♦
    Commented Sep 7, 2019 at 17:35
  • $\begingroup$ @whuber The reference i'm reading used triangular distributions and discretized them with arbitrary sampling step to form a discrete distribution. $\endgroup$
    – nauok
    Commented Sep 8, 2019 at 6:55
  • $\begingroup$ @whuber you mean if we have just the PDFs the complexity may be higher order it just adds additional sums to the computations. $\endgroup$
    – nauok
    Commented Sep 8, 2019 at 6:58
  • 1
    $\begingroup$ Cross-posted: cs.stackexchange.com/q/116022/755, stats.stackexchange.com/q/425318/2921. Please do not post the same question on multiple sites. $\endgroup$
    – D.W.
    Commented Oct 20, 2019 at 18:50

0

Reset to default