Growth Rates of Functions

Core Definition

In mathematical analysis and engineering algorithm design, the relative growth rate of two functions as $x \to \infty$ describes which function dominates asymptotically.

A function $g(x)$ is said to grow faster than $f(x)$ as $x \to \infty$ if:

\lim_{x \to \infty} \frac{f(x)}{g(x)} = 0 \quad \left(\text{or equivalently, } \lim_{x \to \infty} \frac{g(x)}{f(x)} = \infty\right)

Two functions have comparable growth rates if

\lim_{x \to \infty} \frac{f(x)}{g(x)} = M

for some non-zero finite constant

M > 0

Concept Explanation

1. The Asymptotic Dominance Hierarchy

When evaluating limits at infinity involving ratios of disparate function families, L'Hôpital's Rule rigorously confirms the universal hierarchy of asymptotic growth:

\ln(\ln x) \ll \ln x \ll x^p \ll a^x \ll x! \ll x^x \qquad (p > 0, \; a > 1)

  Rate of Growth as x ──> ∞
   ▲
   │                                   / Exponential (e^x, 2^x)
   │                                 /
   │                               /  / Power / Polynomial (x^3, x^2)
   │                             /  /
   │                           /  /  / Linear (x)
   │                         /  /  /
   │                       /  /  /  / Square Root (x^0.5)
   │                     /  /  /  /
   │                   /  /  /  /  / Logarithmic (ln x)
   │                 /  /  /  /  /
   0────────────────────────────────────────► x

2. Proof of Exponential Dominance via L'Hôpital's Rule

Consider the ratio of any positive integer power of $x$ to the natural exponential $e^x$ :

\lim_{x \to \infty} \frac{x^n}{e^x}

Direct substitution gives the indeterminate form

\frac{\infty}{\infty}

. Applying L'Hôpital's Rule

n

consecutive times:

\lim_{x \to \infty} \frac{x^n}{e^x} \overset{\text{L'H}}{=} \lim_{x \to \infty} \frac{n x^{n-1}}{e^x} \overset{\text{L'H}}{=} \lim_{x \to \infty} \frac{n(n-1)x^{n-2}}{e^x} = \cdots = \lim_{x \to \infty} \frac{n!}{e^x}

Because the numerator is reduced to a static constant (

n!

) while the denominator continues to grow without bound (

e^x \to \infty

), the limit is strictly:

\lim_{x \to \infty} \frac{n!}{e^x} = 0

Fundamental Takeaway: Any exponential function with base

a > 1

eventually outgrows any polynomial function, no matter how large the power

n

or how small the base

a

3. Logarithmic Subordinance

Similarly, the natural logarithm grows slower than any positive power of $x$ , even extremely small fractional powers like $x^{0.01}$ :

\lim_{x \to \infty} \frac{\ln x}{x^p} \overset{\text{L'H}}{=} \lim_{x \to \infty} \frac{\frac{1}{x}}{p x^{p-1}} = \lim_{x \to \infty} \frac{1}{p x^p} = 0 \quad (p > 0)

This mathematical reality underpins the extreme efficiency of binary search trees and logarithmic database indexing algorithms in computer engineering.

Engineering Applications

Computer Science & Software Engineering (Algorithmic Complexity): The Big- $O$ runtime efficiency of search and sorting algorithms is governed by growth rates. Algorithms scaling as $O(\log n)$ or $O(n \log n)$ (like MergeSort) remain highly performant for billion-element datasets, whereas $O(n^2)$ or $O(2^n)$ algorithms suffer exponential execution timeouts.
Electrical & Control Engineering (Transient Decay vs. Steady State): In circuit stability analysis, transient decay terms governed by $e^{-\alpha t} t^k$ must vanish as $t \to \infty$ . L'Hôpital's Rule proves that negative exponential dampening always overpowers polynomial voltage surges.

Example Problems

Example 1: Comparing Polynomial and Exponential Growth

Evaluate $\lim_{x \to \infty} \frac{3x^2 + 500x}{e^{0.2x}}$ .

Solution

Step 1: Check form As $x \to \infty$ , both numerator and denominator diverge to $\infty$ . Form: $\frac{\infty}{\infty}$ .

Step 2: First application of L'Hôpital's Rule

\lim_{x \to \infty} \frac{3x^2 + 500x}{e^{0.2x}} \overset{\text{L'H}}{=} \lim_{x \to \infty} \frac{6x + 500}{0.2 e^{0.2x}}

Form:

\frac{\infty}{\infty}

Step 3: Second application of L'Hôpital's Rule

\lim_{x \to \infty} \frac{6x + 500}{0.2 e^{0.2x}} \overset{\text{L'H}}{=} \lim_{x \to \infty} \frac{6}{(0.2)^2 e^{0.2x}} = \lim_{x \to \infty} \frac{6}{0.04 e^{0.2x}} = \lim_{x \to \infty} \frac{150}{e^{0.2x}}

Step 4: Evaluate As $x \to \infty$ , $e^{0.2x} \to \infty$ , so:

\frac{150}{\infty} = 0

Example 2: Comparing Logarithms and Roots

Evaluate $\lim_{x \to \infty} \frac{(\ln x)^3}{\sqrt{x}}$ .

Solution

Step 1: Form $\frac{\infty}{\infty}$ .

Step 2: Differentiate Using the Chain Rule on the numerator:

\lim_{x \to \infty} \frac{3(\ln x)^2 \cdot \frac{1}{x}}{\frac{1}{2\sqrt{x}}} = \lim_{x \to \infty} \frac{6(\ln x)^2}{\sqrt{x}}

Step 3: Successive applications Repeating L'Hôpital's Rule two more times will reduce the numerator powers of $\ln x$ until only a constant remains in the numerator while $\sqrt{x}$ remains in the denominator. Therefore:

\lim_{x \to \infty} \frac{(\ln x)^3}{\sqrt{x}} = 0

Connections & References

Parent Concepts:
- Limits at Infinity
- L'Hôpital's Rule
Related Notes:
- Indeterminate Forms
Course Sessions:
- Session 12 - L’Hopital’s Rule and Indeterminate Forms

Tony's Intertwingled Memex • Reference Manual