# Is there a precise definition for big O notation with 2 or more variables [closed]

Big O notation has a very precise definition for 1 variable. You can prove O(2x^2) = O(x^2) for example. There is never ambiguity. However, for 2 or more variables the definition gets muddy.

Often you might have algorithms with a run time like: O(m + n*k). Intuitively I understand this means it will grow linearly if 2 out of 3 variables are held constant, linear if m=k or m=n and quadratic if n=k. However, I have not found any formal logic surrounding what are or are not valid transformations for big O of multiple variables.

My intuition breaks down in more complex cases though. What if you have O(m + n log(m)) or O(m n ^ 2 + m ^ 2) or O(m^n + m^3) or O(mno + log(mn) + log(o)^m). Some of these might not even make sense, or simplify to something completely different.

My question is this: Is there a exact definition for big O with multiple variables? and is there a algorithm to simplify such expressions to the simplest form like there exists for normal big O.

• Nov 18, 2021 at 13:07
• for each situation, there's a precise definition. I doubt there's a precise definition that applies to all situations Nov 18, 2021 at 19:04
• The statement $f(n,m) = O(g(n, m))$ has a simple interpretation: there is a positive constant $c$ (independent of $n$ and $m$) such that $f(n, m) \le c\, g(n, m)$ on all but finitely many inputs $(n,m)$ in the domain of $f$. If you intend to restrict to, say, $m=n$ or $m$ bounded by some constant, you can just treat this as a restriction to the domain of $f$. Also, in the common case that $g$ is positively valued over the domain of $f$, the "but finitely many" can be dropped (so that $f(n, m)\le c\, g(n,m)$ for all inputs in the domain of $f$). Nov 20, 2021 at 15:12
• On the other hand, by that interpretation, we do have to be careful about the domain. E.g. we do not have $mn+1 = O(mn)$ for $m,n\ge 0$. Or $mn=O((m-1)(n-1))$ for $m,n\ge 1$. So to be precise about what meaning we intend, we'd have to say something like $mn = O((m-1)(n-1))$ for all sufficiently large $m$ and $n$. Feb 23 at 17:28

Here is a definition of $$O$$ for one variable from Cormen, Introduction to Algorithms:

$$f(n) = O(g(n))$$ means there exist positive constants $$c$$ and $$n_0$$ such that $$0 \leq f(n) \leq cg(n)$$ for all $$n \geq n_0$$.

The extension to multiple variables is obvious:

$$f(m,n) = O(g(m,n))$$ means there exist positive constants $$c$$ and $$n_0$$ such that $$0 \leq f(m,n) \leq cg(m,n)$$ for all $$m, n \geq n_0$$.

I don't know if there is an algorithm to simplify these. What is the algorithm you have in mind for $$O$$ for single variables?
• That definition is incorrect (and per the discussion here has been corrected in the latest edition of CLRS). In particular, the "for all $m, n, \ge n_0$" condition should be "for all $m, n$ such that $m\ge n_0$ or $n\ge n_0$." (Consider for example the case when $f(m, n) = 1$ unless $m=1$, in which case $f(1, n) = n$. By your definition $f(m, n) = O(1)$, but this is not the case.) Nov 21, 2021 at 17:28