0
$\begingroup$

Is there a term for $O( (m+n) \log{mn})$? I remember seeing it often in some context but can't remember.

  • 0
    Could show why $O(\log{m}+\log{n}) = O(\log{(m+n)})$ in an answer?2012-11-14

1 Answers 1

1

Note that $O(\log mn)$ is the same class as $O(\log(m+n))$.

Assume $m,n\ge 1$ (since only the behavior for large $m$ and $n$ interests us). Then in one direction we have $\log mn = \log m + \log n \le 2 \max(\log m,\log n) \le 2\log\max(m,n) \le 2\log(m+n)$ and in the other direction $\log(m+n) \le \log(2\max(m,n)) = 1+\max(\log m,\log n) \le 1 + (\log m + \log n) = 1+\log mn$

Therefore $O((m+n)\log mn)$ is just $O(k\log k)$ for $k=m+n$.