0
$\begingroup$

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

  • 1
    Note that it's the same class as $O((m+n)\log(m+n))$ which is just $O(n\log n)$ with $n_{\rm new} = m+n_{\rm old}$.2012-11-14
  • 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$.