Growth of functions

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?

Answer

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

Blog

Search This Blog