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).

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

1 Answer 1


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.

See Wikipedia for similar properties of big O: http://en.wikipedia.org/wiki/Big_O_notation#Properties.

  • 1
    $\begingroup$ 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? $\endgroup$ Oct 15, 2015 at 8:07
  • $\begingroup$ @TomvanderZanden Edited. $\endgroup$ Oct 15, 2015 at 21:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.