0
$\begingroup$

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.

$\endgroup$
4
  • 3
    $\begingroup$ See e.g. math.stackexchange.com/questions/96809/…, cs.stackexchange.com/questions/7480/…. $\endgroup$ Nov 18, 2021 at 13:07
  • $\begingroup$ for each situation, there's a precise definition. I doubt there's a precise definition that applies to all situations $\endgroup$ Nov 18, 2021 at 19:04
  • 2
    $\begingroup$ 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$). $\endgroup$
    – Neal Young
    Nov 20, 2021 at 15:12
  • $\begingroup$ 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$. $\endgroup$
    – Neal Young
    Feb 23 at 17:28

1 Answer 1

1
$\begingroup$

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?

$\endgroup$
1
  • 2
    $\begingroup$ 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.) $\endgroup$
    – Neal Young
    Nov 21, 2021 at 17:28

Not the answer you're looking for? Browse other questions tagged or ask your own question.