Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Is it true that $O(M^3 + NM^2) \, = \, O(M^3 + N)$, where $M$ and $N$ are variables of the function?

share|cite|improve this question
Set $M=0$; then $M^3 + NM^2$ vanishes, but $M^3 + N$ does not. – user1119 Dec 16 '10 at 16:43
Technically, setting M=0 doesn't quite work, since the bound only has to hold for all M,N sufficiently large. – Jeremy Hurwitz Dec 16 '10 at 17:50

[Throughout this answer, I'm going to use set notation in order to be pedantic.]

It is true that $O(M^3+N)\subset O(M^3+NM^2)$, since for $M$ sufficiently large, $c(M^3+N)<c(M^3+NM^2)$. It's worth noting that for $M$ sufficiently close to $0$, $M^3+N>M^3+NM^2$.

For the reverse inclusion, consider $f(M,N)=M^3+NM^2$. Clearly $f\in O(M^3+NM^2)$. We now need to show that for all $c$ and arbitrarily large $M,N$ that $f(M,N)>c(M^3+N)$. We can do this by setting $M=\log N$. We then have $f(\log N,N)=\log^3 N + N\log^2 N$, which is clearly larger than $c(\log^3 N + N)$ for all sufficiently large $N$. So $f(M,N)\not\in O(M^3+N)$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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