Asymptotic Analysis for two variables?

Question

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?

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