Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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?

share|improve this question
    
Highly related: What is the meaning of O(m+n)? –  Juho Dec 18 '12 at 16:40

1 Answer 1

up vote 7 down vote accepted

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

share|improve this answer
    
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. –  sas Dec 18 '12 at 15:41
    
It is definitely "and". –  Marc Khoury Dec 18 '12 at 17:23

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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