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?

  • $\begingroup$ 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… $\endgroup$
    – F'x
    Commented Apr 15, 2012 at 7:42
  • 2
    $\begingroup$ One way that often works to get basic info is to take a series expansion at infinity, say, Series[f[x],{x,Infinity,1}] $\endgroup$ Commented Apr 15, 2012 at 14:31

2 Answers 2


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


Here's a function bigOSimplify that takes an expression and tries to simplify the O(expr) as a function of n:

maxBigO[l_, n_] := Switch[Length@l,
    1, First@l,
    2, If[Limit[Abs[First@l / Last@l], n -> Infinity] === 0, Last@l, First@l],
    _, maxBigO[{maxBigO[Take[l, 2], n], maxBigO[Drop[l, 2], n]}, n]
bigOSimplify[expr_, n_] := 1 /; FreeQ[expr, n];
bigOSimplify[expr_Plus, n_] := bigOSimplify[maxBigO[expr, n], n];
bigOSimplify[expr_Times, n_] := (If[FreeQ[#, n], 1, bigOSimplify[#, n]] &) /@ expr;
bigOSimplify[a_Plus ^ b_, n_] := maxBigO[a, n] ^ b;
bigOSimplify[expr_, n_] := bigOSimplify[FunctionExpand@expr, n] /; expr =!= FunctionExpand@expr;
bigOSimplify[expr_, n_] := expr;


bigOSimplify[2 n^4 + Log[n] + n ^ 2, n] (* => n^4 *)
bigOSimplify[Fibonacci[n], n] (* => (1/2 (1+Sqrt[5]))^n *)

It might give wrong answers for complex expressions, so check the result with F'x's answer.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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