2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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). ​ ​ ​ ​ $\endgroup$ – user12859 Feb 7 '17 at 7:32
4
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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)$? $\endgroup$ – Zhengqun Koo Feb 6 '17 at 14:51
  • $\begingroup$ @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)$. $\endgroup$ – David Richerby Feb 6 '17 at 14:54
  • $\begingroup$ Ok, thank you so much! Did you mean to say "If $m$ does depend on $n$, $m$ must get smaller as $n$ gets bigger"? $\endgroup$ – Zhengqun Koo Feb 6 '17 at 14:59
  • $\begingroup$ @KooZhengqun Yes, sorry for the typo. $\endgroup$ – David Richerby Feb 6 '17 at 15:15
0
$\begingroup$

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.

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

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.