0
$\begingroup$

I came across the following statement in my Computer Science high-school textbook (I translated it to English).

There was some for loop that runs $m$ times nested inside a for loop that runs $n$ times, and it said:

"The function is $n \cdot m$, and since $n$ and $m$ are as large as we want, we can set $m$ equal to $n$ and say that the complexity is $O(n^2).$"

Obviously I was suspicious, because $m$ in this case didn't depend on $n$.

So I started thinking about the problem with the big-$O$ definition.

Using the definition of for multiple variables, I proved the statement is false by contradiction.

I also thought about using the definition for a single variable, with $m$ as a function of $n$. I was able to prove that $n \cdot m = O(n^2)$ if and only if $m=O(n)$.

My question is, is it possible to somehow generalize this thought and say that $f(n,m) = O(f(n,n))$ if some properties hold? Is this even legal, with Big-$O$ notation?

I'm also not sure if my original proofs are correct, so here they are:

Using the multiple variable definition, prove $n \cdot m \neq O(n^2)$.

Suppose $n \cdot m = O(n^2)$, then there exist $c,n_0,m_0 \in \mathbb{R}_{>0}$ so that $n \geq n_0, m \geq m_0$ implies $n \cdot m \leq cn^2$. But if we look at $n=n_0,m=\max(m_0,cn_0+1)$, we have $$n \cdot m = n_0 \cdot \max(m_0,cn_0+1) \geq n_0 \cdot (cn_0+1) = cn_0^2+n_0 > cn_0^2$$ This is a contradiction, because $n=n_0 \geq n_0$ and $m=\max(m_0,cn_0+1) \geq m_0$ and so we should have $n \cdot m \leq cn^2 = cn_0^2$.

Using the single variable definition, prove $n \cdot m = O(n^2) \iff m=O(n)$.

Suppose $n \cdot m = O(n^2)$, then there exist $c,n_0 \in \mathbb{R}_{>0}$ so that $n \geq n_0$ implies $n \cdot m \leq cn^2$. Divide both sides by $n$, and we have $m \leq cn$ for $n \geq n_0$, which directly means (by definition) that $m=O(n)$.

Suppose $m = O(n)$, then there exist $c,n_0 \in \mathbb{R}_{>0}$ so that $n \geq n_0$ implies $m \leq cn$. Now let's prove $n \cdot m = O(n^2)$. For every $n$ and specifically for every $n \geq n_0$, $$n \cdot m \leq n \cdot cn = cn^2$$ Which directly means (by definition) that $n \cdot m = O(n^2)$.

$\endgroup$
  • $\begingroup$ $m$ must depend on $n$ in some way, otherwise $mn=O(n)\ne O(n^2)$ $\endgroup$ – Exodd Nov 30 '18 at 9:34
  • $\begingroup$ Yes. As I wrote, we think of m as a function of n. $\endgroup$ – user554564 Nov 30 '18 at 10:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy