Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

Does somebody know if Mathematica can be used to calculate the growth of functions, that is in Big O, Theta, and Omega and find proper $n_{0}$ and $c_{1}$, $c_{2}$ respectively?

share|improve this question
    
Hi JanosAudron, and welcome to Mathematica StackExchange! I'm afraid that while quantities such as $n_0$, $c_1$ and $c_2$ typically appear in formal definitions of the big-O (and related) notations, one most often does not calculate them explicitly to prove domination relations between functions… –  F'x Apr 15 '12 at 7:42
1  
One way that often works to get basic info is to take a series expansion at infinity, say, Series[f[x],{x,Infinity,1}] –  Daniel Lichtblau Apr 15 '12 at 14:31
add comment

1 Answer 1

up vote 16 down vote accepted

Yes, Mathematica can be used to characterize the asymptotic behaviour of functions, but maybe not in the straightforward way you intended. Let's see a few examples (I'll focus on asymptotic behaviour as $x\rightarrow\infty$, but behaviour around any other point works the same) of what we can do by looking at limits (using the Limit function):


How to check if $f(x) \in o(g(x))$, or $g(x) \in \omega(f(x))$

There, the question we can ask Mathematica is: what is the limit of $f(x)/g(x)$:

  • If the limit is zero, then $f$ is dominated by $g$, as in the example below, where $$f(x)=x^2e^{-\sqrt x}\ \ \text{ and }\ \ g(x)=e^{-x}$$

    In[1]:= Limit[(x^2*Exp[-Sqrt[x]])/Exp[x], x -> ∞]
    Out[1]= 0
    
  • If the limit exists, but is not zero (it can be a finite number, an infinity, or an Interval): $f$ is not dominated by $g$ (and if the limit is $\infty$, then in fact $g$ is dominated by $f$). Three examples:

    In[2]:= Limit[(3*x^2 + x + 1)/x^2, x -> ∞]
    Out[2]= 3
    
    In[3]:= Limit[Gamma[x]/Exp[x], x -> ∞]
    Out[3]= ∞
    
    In[4]:= Limit[x*Sin[x]/Sqrt[x], x -> ∞]
    Out[4]= Interval[{0, ∞}]
    
  • If the limit is unknown to Mathematica, then you haven't learnt anything.


How to check if $f(x) \in O(g(x))$

$f(x) \in O(g(x))$ means that, for large enough $x$, $\left\vert f(x)/g(x)\right\vert$ is bounded. So, our options are as such:

  • If $\left|f(x)/g(x)\right|$ converges to a finite number (including zero, but not $\infty$), then that's it: $f(x) \in O(g(x))$

    In[5]:= Limit[(3*x^2 + x + 1)/(Erf[x]*x^2), x -> ∞]
    Out[5]= 3
    
  • If $|f(x)/g(x)|$ converges to an interval which does not include any infinity, the same is true:

    In[6]:= Limit[Abs[Sin[x]/(2 + Cos[x])], x -> ∞]
    Out[6]= Interval[{0, 1}]
    
  • If $\left|f(x)/g(x)\right|$ converges to $\infty$ or to an interval containing $\infty$, then $f(x) \not\in O(g(x))$.

  • Otherwise, you have learnt nothing.


The fine print: in many examples above, I calculate $f/g$ instead of $|f/g|$ because I know that the functions both have positive values. Also, if $g(x)$ takes zero as a value in more than a finite number of points, you need to be a little bit more careful than just calculating $f/g$.

share|improve this answer
add comment

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.