2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Mh, maybe $m\,O(\log n) = O(m \log n)$ ? $\endgroup$ – Yves Daoust Oct 15 '15 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 '15 at 2:16
  • 1
    $\begingroup$ Are we clear about what Landau notation in two variables means? $\endgroup$ – Raphael Oct 16 '15 at 7:55
1
$\begingroup$

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.

$\endgroup$
  • 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$ – Tom van der Zanden Oct 15 '15 at 8:07
  • $\begingroup$ @TomvanderZanden Edited. $\endgroup$ – MasterOfBinary Oct 15 '15 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.