[Solved]: Asymptotic Analysis for two variables?

Problem Detail: 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?

Asked By : sas

Answered By : Marc Khoury

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$.
Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/7480