🌱 Tony's Memex Tony's Intertwingled Memex
Digital Garden | OER Curriculum
Home / Digital Garden / Growth Rates of Functions

Growth Rates of Functions

πŸ–¨οΈ Printable Reference / PDF
Core Definition

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

A function g(x)g(x) is said to grow faster than f(x)f(x) as xβ†’βˆžx \to \infty if:

lim⁑xβ†’βˆžf(x)g(x)=0(orΒ equivalently,Β lim⁑xβ†’βˆžg(x)f(x)=∞)\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β†’βˆžf(x)g(x)=M\lim_{x \to \infty} \frac{f(x)}{g(x)} = M for some non-zero finite constant M>0M > 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)β‰ͺln⁑xβ‰ͺxpβ‰ͺaxβ‰ͺx!β‰ͺxx(p>0,β€…β€Ša>1)\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 xx to the natural exponential exe^x:

lim⁑xβ†’βˆžxnex\lim_{x \to \infty} \frac{x^n}{e^x}
Direct substitution gives the indeterminate form ∞∞\frac{\infty}{\infty}. Applying L'Hôpital's Rule nn consecutive times:
lim⁑xβ†’βˆžxnex=L’Hlim⁑xβ†’βˆžnxnβˆ’1ex=L’Hlim⁑xβ†’βˆžn(nβˆ’1)xnβˆ’2ex=β‹―=lim⁑xβ†’βˆžn!ex\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!n!) while the denominator continues to grow without bound (exβ†’βˆže^x \to \infty), the limit is strictly:
lim⁑xβ†’βˆžn!ex=0\lim_{x \to \infty} \frac{n!}{e^x} = 0
Fundamental Takeaway: Any exponential function with base a>1a > 1 eventually outgrows any polynomial function, no matter how large the power nn or how small the base aa.

3. Logarithmic Subordinance

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

lim⁑xβ†’βˆžln⁑xxp=L’Hlim⁑xβ†’βˆž1xpxpβˆ’1=lim⁑xβ†’βˆž1pxp=0(p>0)\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-OO runtime efficiency of search and sorting algorithms is governed by growth rates. Algorithms scaling as O(log⁑n)O(\log n) or O(nlog⁑n)O(n \log n) (like MergeSort) remain highly performant for billion-element datasets, whereas O(n2)O(n^2) or O(2n)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βˆ’Ξ±ttke^{-\alpha t} t^k must vanish as tβ†’βˆž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β†’βˆž3x2+500xe0.2x\lim_{x \to \infty} \frac{3x^2 + 500x}{e^{0.2x}}.

Solution

Step 1: Check form As xβ†’βˆž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β†’βˆž3x2+500xe0.2x=L’Hlim⁑xβ†’βˆž6x+5000.2e0.2x\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β†’βˆž6x+5000.2e0.2x=L’Hlim⁑xβ†’βˆž6(0.2)2e0.2x=lim⁑xβ†’βˆž60.04e0.2x=lim⁑xβ†’βˆž150e0.2x\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β†’βˆžx \to \infty, e0.2xβ†’βˆže^{0.2x} \to \infty, so:

150∞=0\frac{150}{\infty} = 0

Example 2: Comparing Logarithms and Roots

Evaluate lim⁑xβ†’βˆž(ln⁑x)3x\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β†’βˆž3(ln⁑x)2β‹…1x12x=lim⁑xβ†’βˆž6(ln⁑x)2x\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\ln x until only a constant remains in the numerator while x\sqrt{x} remains in the denominator. Therefore:

lim⁑xβ†’βˆž(ln⁑x)3x=0\lim_{x \to \infty} \frac{(\ln x)^3}{\sqrt{x}} = 0

Connections & References