Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
3  
Set $M=0$; then $M^3 + NM^2$ vanishes, but $M^3 + N$ does not. –  user1119 Dec 16 '10 at 16:43
1  
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
add comment

1 Answer 1

[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|improve this answer
add comment

Your Answer

 
discard

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.