largest samples of set of random variables 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 &lt; k) + pr(X &lt; k) pr(Y = k) + pr(X = k) pr(Y=k)$



Where in the above figure pr(Z=3) for instance is pr(X=3)*pr(Y=3)+ pr(X&lt;3)pr(Y=3)+ pr(X=3)pr(Y&lt;3) so (1)(1) + (1+1)(1) + (1)(1+1+1) =7.

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?

According to my calculations there is only 2 multiplications and n sums involve to generate each sample, so it should be o(n), right?
Yes, you are right; the PDF of $Z=\max(X,Y)$ can be computed from the PDFs for $X,Y$ in $O(n+m)$ time, using the approach you described.

In particular, it takes $O(n)$ time to compute $P(X&lt;x)$ for each $x$ ($n$ sums), $O(m)$ time to compute $P(Y&lt;y)$ for each $y$ ($m$ sums), and $O(n+m)$ time to then compute $P(Z=z)$ for each $z$ (3 products and 2 sums for each of the possible values of $z$).

Perhaps that paper was using a sub-optimal algorithm, or maybe it was just a mistake, or maybe the author didn't care about the difference between $O(n+m)$ vs $O(nm)$ and used an overly loose bound.