How is asymptotic analysis (big o, little o, big theta, big theta etc.) defined for functions with multiple variables?

I know that the Wikipedia article has a section on it, but it uses a lot of mathematical notation which I am unfamiliar with it. I also found the following paper: http://people.cis.ksu.edu/~rhowell/asymptotic.pdf However the paper is very long and provides a complete analysis of asymptotic analysis rather than just giving a definition. Again the frequent usage of mathematical notation made it very hard to understand.

Could someone provide a definition of asymptotic analysis without the complex mathematical notation?


1 Answer 1


Asymptotic notation for multivariable functions is defined analogously to its single variable counterpart. In the single variable case, we say that $f(n) \in O(g(n))$ if and only if there exists constants $C,N$ such that for all $n > N$ we have $f(n) \leq Cg(n)$. In other words $f(n)$ is upper bounded by some multiple of $g(n)$ for all $n$ larger than some fixed $N$.

In the multivariate case, the definition is nearly the same, except you have a few more variables to worry about. Let's suppose $f(n,m)$ is a function of two variables. We want to bound $f$ from above by another function of two variables. So we say that $f(n,m) \in O(g(n,m))$ if and only if there exists constants $C,N$ such that for all $n>N$ and $m>N$ we have $f(n,m) \leq Cg(n,m)$. The definition is nearly exactly the same, except now all of our variables must be greater than our fixed constant $N$.

The wikipedia article used $\overrightarrow{x}$ to mean a vector in $\mathbb{R}^d$ which would mean that $f$ and $g$ were multivariable functions of $d$ variables (i.e. $f,g:\mathbb{R}^d \rightarrow \mathbb{R}$). Saying that $x_i > N$ for all $i$ meant that each component of $\overrightarrow{x}$ had to be greater than $N$.

  • 4
    $\begingroup$ Thanks! Just confirming, but is the definition: (1)"for all n>N and m>N" or (2)"for all n>N or m>N"? You and Wikipedia use the "and" definition, however CLRS uses the "or" definition. $\endgroup$
    – sas
    Dec 18, 2012 at 15:41
  • 1
    $\begingroup$ It is definitely "and". $\endgroup$ Dec 18, 2012 at 17:23
  • 2
    $\begingroup$ @MarcKhoury No, it's definitely "or" - if this general shape of formalization is correct at all. CLRS has corrected it with the 3rd edition and Wikipedia has followed. See here for a lengthy discussion on why "and" is incorrect in that it leads to intuitively wrong results: cs.stackexchange.com/a/3151/129807 $\endgroup$
    – Mo B.
    Dec 28, 2020 at 17:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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