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$
$\endgroup$
3
-
$\begingroup$ Mh, maybe $m\,O(\log n) = O(m \log n)$ ? $\endgroup$– Yves DaoustOct 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$– usulOct 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
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
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
-