Hierarchy of Infinities: Orders of Growth and Asymptotic Comparison

How two infinities are compared

The fact that two functions both tend to infinity does not mean that they grow at the same rate. To compare their behaviour we must consider them within one and the same limiting process and determine how each varies relative to the other.

Let \(f\) and \(g\) be two functions such that

\[ |f(x)|\to+\infty \qquad\text{and}\qquad |g(x)|\to+\infty \]

as \(x\to x_0\), where \(x_0\) may be a real number, \(+\infty\), or \(-\infty\). To compare their orders of growth, one studies, when it exists, the limit of the ratio of their absolute values:

\[ L=\lim_{x\to x_0}\frac{|f(x)|}{|g(x)|}. \]

This ratio measures the magnitude of \(f(x)\) relative to that of \(g(x)\). If it tends to \(0\), the magnitude of \(f(x)\) becomes negligible compared with that of \(g(x)\); if it tends to a positive real number, the two functions have comparable magnitudes; if it tends to \(+\infty\), then \(f(x)\) dominates \(g(x)\).

When the two functions have the same sign eventually as \(x\to x_0\), the absolute values may be omitted, and one may study directly

\[ \lim_{x\to x_0}\frac{f(x)}{g(x)}. \]

For instance, as \(x\to+\infty\),

\[ \frac{x^2}{x^3}=\frac{1}{x}\to 0. \]

Thus, although \(x^2\) and \(x^3\) both tend to \(+\infty\), the function \(x^2\) grows more slowly than \(x^3\).

The limit of the ratio need not exist. When this happens, the criterion on its own does not immediately allow us to assign to the two functions one of the relations defined in the next section.

Higher, lower, and equal orders of infinity

Let \(f\) and \(g\) be two functions that are infinite as \(x\to x_0\). The limit of the ratio of their absolute values determines their relative order of growth.

If

\[ \lim_{x\to x_0}\frac{|f(x)|}{|g(x)|}=0, \]

then \(f\) is an infinity of lower order than \(g\), while \(g\) is an infinity of higher order than \(f\). One writes

\[ f(x)=o\bigl(g(x)\bigr) \qquad\text{as }x\to x_0. \]

This relation expresses the fact that, although both are infinite, the size of \(f(x)\) becomes negligible compared with that of \(g(x)\).

If instead

\[ \lim_{x\to x_0}\frac{|f(x)|}{|g(x)|}=L, \qquad 0<L<+\infty, \]

then \(f\) and \(g\) are infinities of the same order. The ratio of their absolute values tends neither to \(0\) nor to \(+\infty\): the two functions are therefore of asymptotically comparable size.

Finally, if

\[ \lim_{x\to x_0}\frac{|f(x)|}{|g(x)|}=+\infty, \]

then \(f\) is an infinity of higher order than \(g\). This situation is equivalent to

\[ \lim_{x\to x_0}\frac{|g(x)|}{|f(x)|}=0. \]

For instance, as \(x\to+\infty\),

\[ \frac{3x^2}{5x^2}=\frac{3}{5}. \]

Since the ratio tends to a finite positive number, \(3x^2\) and \(5x^2\) are infinities of the same order. They are not, however, equivalent, since the limit of their ratio is not equal to \(1\): this distinction will be made precise in the next section.

Equivalent infinities

Let \(f\) and \(g\) be two functions that are infinite as \(x\to x_0\). They are said to be equivalent infinities if

\[ \lim_{x\to x_0}\frac{f(x)}{g(x)}=1. \]

In this case one writes

\[ f(x)\sim g(x) \qquad\text{as }x\to x_0. \]

Equivalence means that the ratio of the two functions approaches \(1\): each of them therefore represents, to first order, the asymptotic behaviour of the other.

Two equivalent infinities are necessarily of the same order, but the converse does not always hold. For instance, \(3x^2\) and \(5x^2\) are of the same order as \(x\to+\infty\), yet they are not equivalent, since

\[ \lim_{x\to+\infty}\frac{3x^2}{5x^2}=\frac{3}{5}\neq 1. \]

If, more generally,

\[ \lim_{x\to x_0}\frac{f(x)}{g(x)}=L, \qquad L\in\mathbb{R}\setminus\{0\}, \]

then \(f\) and \(g\) are of the same order, and

\[ f(x)\sim Lg(x). \]

For instance, as \(x\to+\infty\),

\[ \frac{x^2+3x}{x^2}=1+\frac{3}{x}\to 1. \]

Hence

\[ x^2+3x\sim x^2. \]

Asymptotic equivalence is not an equality: it describes only the relative behaviour of the functions in the limiting process considered. For this reason, replacing a function by one equivalent to it must be done with care, above all in sums and differences, where cancellations may occur.

The fundamental hierarchy of infinities

As \(x\to+\infty\), the principal functions tending to \(+\infty\) can be ordered according to their rates of growth. The fundamental families are the logarithmic, power, and exponential functions.

Within the family of powers, if \(0<\alpha<\beta\), then

\[ x^\alpha=o\bigl(x^\beta\bigr). \]

A power with the larger exponent is therefore an infinity of higher order than a power with the smaller exponent.

Likewise, given two exponential functions with base greater than \(1\), if \(1<a<b\), then

\[ a^x=o\bigl(b^x\bigr). \]

For logarithms, by contrast, a change of base introduces only a constant factor. If \(a>1\), then

\[ \log_a(x)=\frac{\ln(x)}{\ln(a)}. \]

Consequently, all logarithmic functions with base greater than \(1\) have the same order of growth. To study the hierarchy, it therefore suffices to fix a single base; in what follows we use the natural logarithm, denoted by \(\ln(x)\).

Comparison across different families leads to the fundamental relations

\[ \bigl(\ln(x)\bigr)^p=o\bigl(x^q\bigr) \qquad\text{and}\qquad x^q=o\bigl(a^x\bigr), \]

valid for all \(p>0\), \(q>0\), and \(a>1\). Thus any positive power of the natural logarithm grows more slowly than any positive power of \(x\), while any positive power of \(x\) grows more slowly than every exponential with base greater than \(1\).

The hierarchy may be extended to include the iterated logarithm and the function \(x^x\):

\[ \ln\bigl(\ln(x)\bigr)=o\bigl(\bigl(\ln(x)\bigr)^p\bigr), \qquad \bigl(\ln(x)\bigr)^p=o\bigl(x^q\bigr), \qquad x^q=o\bigl(a^x\bigr), \qquad a^x=o\bigl(x^x\bigr). \]

This chain does not compare the values of the functions for every \(x\); it describes solely their asymptotic behaviour as \(x\to+\infty\). Each function appearing farther to the right therefore asymptotically dominates all those that precede it.

Applications and worked comparisons

Once the fundamental hierarchy has been established, many comparisons can be resolved simply by recognising the families to which the functions belong, without having to evaluate each ratio by a separate, lengthier argument.

Consider, for instance,

\[ \lim_{x\to+\infty}\frac{\bigl(\ln(x)\bigr)^4}{x^{1/3}}. \]

Every positive power of the natural logarithm grows more slowly than any positive power of \(x\). Hence

\[ \bigl(\ln(x)\bigr)^4=o\bigl(x^{1/3}\bigr) \]

and therefore

\[ \lim_{x\to+\infty}\frac{\bigl(\ln(x)\bigr)^4}{x^{1/3}}=0. \]

Similarly, in the limit

\[ \lim_{x\to+\infty}x^5e^{-x}=\lim_{x\to+\infty}\frac{x^5}{e^x}, \]

the exponential term dominates the power. Since

\[ x^5=o\bigl(e^x\bigr), \]

we obtain

\[ \lim_{x\to+\infty}x^5e^{-x}=0. \]

The hierarchy also allows us to compare functions belonging to the same family. For instance,

\[ \frac{2^x}{5^x}=\left(\frac{2}{5}\right)^x\to 0, \]

so that

\[ 2^x=o\bigl(5^x\bigr) \qquad\text{as }x\to+\infty. \]

A further important application is the identification of the dominant term of a sum. Consider

\[ f(x)=3e^x+7x^4-\bigl(\ln(x)\bigr)^2. \]

Dividing by \(3e^x\), we have

\[ \frac{f(x)}{3e^x}=1+\frac{7x^4}{3e^x}-\frac{\bigl(\ln(x)\bigr)^2}{3e^x}. \]

Since both \(x^4\) and \(\bigl(\ln(x)\bigr)^2\) are of lower order than \(e^x\), the last two terms tend to \(0\). It follows that

\[ \lim_{x\to+\infty}\frac{f(x)}{3e^x}=1, \]

and hence

\[ 3e^x+7x^4-\bigl(\ln(x)\bigr)^2\sim 3e^x. \]

Asymptotic equivalence is preserved under products and quotients: if \(f\sim g\) and \(h\sim k\) in the same limiting process, then \(fh\sim gk\) and, provided \(h\) and \(k\) are eventually non-zero, \(\displaystyle\frac{f}{h}\sim\frac{g}{k}\). In sums and differences, by contrast, a function cannot be replaced indiscriminately by one equivalent to it. For instance,

\[ x^2+x\sim x^2, \]

but in the difference

\[ (x^2+x)-x^2=x, \]

the dominant terms cancel. Replacing \(x^2+x\) by its equivalent \(x^2\) would thus discard precisely the term that determines the result.