How to compute largest values of random variables? [closed]

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:

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?

• 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?
– whuber
Sep 7 '19 at 17:35
• @whuber The reference i'm reading used triangular distributions and discretized them with arbitrary sampling step to form a discrete distribution. Sep 8 '19 at 6:55
• @whuber you mean if we have just the PDFs the complexity may be higher order it just adds additional sums to the computations. Sep 8 '19 at 6:58
• – D.W.
Oct 20 '19 at 18:50