Generalizing $n \cdot m = O(n^2) \iff m = O(n)$ to any two-variable function

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

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