<p>Here is a definition of <span class="math-container">$O$</span> for one variable from Cormen, Introduction to Algorithms:</p>
<p><span class="math-container">$f(n) = O(g(n))$</span> means there exist positive constants <span class="math-container">$c$</span> and <span class="math-container">$n_0$</span> such that <span class="math-container">$0 \leq f(n) \leq cg(n)$</span> for all <span class="math-container">$n \geq n_0$</span>.</p>
<p>The extension to multiple variables is obvious:</p>
<p><span class="math-container">$f(m,n) = O(g(m,n))$</span> means there exist positive constants <span class="math-container">$c$</span> and <span class="math-container">$n_0$</span> such that <span class="math-container">$0 \leq f(m,n) \leq cg(m,n)$</span> for all <span class="math-container">$m, n \geq n_0$</span>.</p>
<p>See also the pages linked to by Emil Jeřábek.</p>
<p>I don't know if there is an algorithm to simplify these. What is the algorithm you have in mind for <span class="math-container">$O$</span> for single variables?</p>

CC BY-SA 4.0
2021-11-21T17:28:32.850Z
That definition is incorrect (and per the discussion [here](https://cs.stackexchange.com/questions/7480/asymptotic-analysis-for-two-variables) 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.)
Neal Young
CC BY-SA 4.0
2021-11-21T15:52:02.520Z
2021-11-21T15:52:02.520Z
toby544
<p>Big O notation has a very precise definition for 1 variable. You can prove <code>O(2x^2) = O(x^2)</code> for example. There is never ambiguity. However, for 2 or more variables the definition gets muddy.</p>
<p>Often you might have algorithms with a run time like: <code>O(m + n*k)</code>. 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.</p>
<p>My intuition breaks down in more complex cases though. What if you have O(m + n log(m)) or <code>O(m n ^ 2 + m ^ 2)</code> or <code>O(m^n + m^3)</code> or <code>O(mno + log(mn) + log(o)^m)</code>. Some of these might not even make sense, or simplify to something completely different.</p>
<p>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.</p>

CC BY-SA 4.0
2021-11-18T13:07:23.113Z
See e.g. https://math.stackexchange.com/questions/96809/formal-definition-of-big-o-when-multiple-variables-are-involved, https://cs.stackexchange.com/questions/7480/asymptotic-analysis-for-two-variables.
Emil Jeřábek
CC BY-SA 4.0
2021-11-18T19:04:45.627Z
for each situation, there's a precise definition. I doubt there's a precise definition that applies to all situations
mathworker21
CC BY-SA 4.0
2021-11-20T15:12:21.297Z
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$).
Neal Young
CC BY-SA 4.0
2022-02-23T17:28:48.950Z
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$*.
Neal Young
<complexity-classes>
Is there a precise definition for big O notation with 2 or more variables
mousetail 'he-him'
# Is there a precise definition for big O notation with 2 or more variables

(Asked by: username_0 on 2021-11-18)

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.

**Tags:** complexity-classes
> **Comments:**
> **username_1**: See e.g. https://math.stackexchange.com/questions/96809/formal-definition-of-big-o-when-multiple-variables-are-involved, https://cs.stackexchange.com/questions/7480/asymptotic-analysis-for-two-variables.  
> **username_2**: for each situation, there's a precise definition. I doubt there's a precise definition that applies to all situations  
> **username_3**: 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$).  
> **username_3**: 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$*.  

---

## 1 answers

### Answer by username_4 on 2021-11-21. Score: 1 | Accepted answer

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

See also the pages linked to by Emil Jeřábek.

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?

> **Comments:**
> **username_3**: That definition is incorrect (and per the discussion [here](https://cs.stackexchange.com/questions/7480/asymptotic-analysis-for-two-variables) 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.)  

---

