I am confused as to how this is true: O(n log n) + mO(log n) = O((m + n) log n)

I understand that O(n) + O(m) = O(n + m). I'm mostly confused as to how to deal with the coefficient preceding O(log n).

• Mh, maybe $m\,O(\log n) = O(m \log n)$ ? Oct 15, 2015 at 7:28
• So/well, what does this equation mean exactly? ($O(n\log n) + m O(\log n) = O((m+n)\log n)$?
– usul
Oct 16, 2015 at 2:16
• Are we clear about what Landau notation in two variables means?
– Raphael
Oct 16, 2015 at 7:55

We can prove that if $f(n)$ is $O(\log{n})$ and $g(m)$ is $O(m)$ then $f(n)g(m)$ is $O(m \log{n})$. To say that $mO(\log{n}) = O(m \log{n}))$ is an abuse of notation.
• From what does it follow that $g(n)=\log n$? Where does it say that you can "multiply both sides by m"? What does $mO(\log n)$ even mean? $mO(\log n)$ is not a function, so how can you say it is $O$-anything? Oct 15, 2015 at 8:07