# Simplified big O notation of $O(nm)$ for $n\gg m$

Assume $n$ is much greater than $m$. Would $O(nm)$ simplify to $O(n)$? Is there an explanation?

• If m is at most polylogarithmic in n, then ​ $O(n\hspace{-0.04 in}\cdot \hspace{-0.04 in}m)$ ​ can be expressed as Õ(n). ​ ​ ​ ​ – user12859 Feb 7 '17 at 7:32

It depends what "$n$ is much greater than $m$" means but, in general, no. For example, one common definition of "much greater" is that $m=o(n)$. But, in this case, we can still have, e.g., $m=n^\epsilon$ for some $\epsilon<1$, or $m=\log^c n$ for any $c\geq 0$ and, in both of these cases, $nm\neq O(n)$.

To get $nm=O(n)$, you need $m=O(1)$.

• So you're saying, I can only simplify to $O(n)$ if $m$ is a constant. And if $m$ depends on $n$ in any way, then I cannot simplify, I will have to write out the full $O(nm)$? – Zhengqun Koo Feb 6 '17 at 14:51
• @KooZhengqun No, $m$ has to be bounded above by a constant, and it might depend on $n$. If it does depend on $n$, it must get smaller as $m$ gets bigger. For example, if $m=n^{-c}$ for any $c\ge0$, then $nm\in O(n^{1-c})\subseteq O(n)$. – David Richerby Feb 6 '17 at 14:54
• Ok, thank you so much! Did you mean to say "If $m$ does depend on $n$, $m$ must get smaller as $n$ gets bigger"? – Zhengqun Koo Feb 6 '17 at 14:59
• @KooZhengqun Yes, sorry for the typo. – David Richerby Feb 6 '17 at 15:15

If an algorithm depends on both you cannot. Example can be a matrix operation where the size of a matrix is mxn. Even if you have 1000 rows (n) and only 2 columns (m), it's still a mxn complexity problem, not 2n, because m is not constant, it may vary.

• Why would anybody imagine that $mn$ is the same thing as $2n$? Did you mean $n^2$? – David Richerby Feb 7 '17 at 11:47
• In the example above, in case you want to treat m as a constant. Which is not right, even if m is small – blade Feb 7 '17 at 14:34
• OK, but why specifically $2n$ -- that looks like $m+n$ where $m\approx n$. – David Richerby Feb 7 '17 at 15:29