largest samples of set of random variables
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.