L'Hôpital's rule · Calculus × Computing

What is it?

For indeterminate forms $0/0$ or $\infty/\infty$ , $\lim \frac fg = \lim \frac{f'}{g'}$ when the right-hand limit exists. It settles races between growth rates, such as $\log n$ versus $n^\varepsilon$ .

Statement

If $f(x), g(x) \to 0$ (or both $\to \pm\infty$ ) as $x \to a$ , $g' \ne 0$ near $a$ , and $\lim_{x\to a}\frac{f'(x)}{g'(x)} = L$ , then $\lim_{x\to a}\frac{f(x)}{g(x)} = L$ .

Idea of the proof

Extend $f, g$ by $0$ at $a$ and apply Cauchy's MVT on $[a, x]$ : $\frac{f(x)}{g(x)} = \frac{f'(c_x)}{g'(c_x)}$ with $c_x \to a$ .

Formulas

$\lim_{n\to\infty}\frac{\ln n}{n^{\varepsilon}} = \lim_{n\to\infty}\frac{1/n}{\varepsilon n^{\varepsilon - 1}} = \lim_{n\to\infty}\frac{1}{\varepsilon n^{\varepsilon}} = 0$
logarithms lose against any power

Where it shows up in computing

Algorithm analysis and complexity★★★★★frequentScientific computing and algorithms
Proves the growth hierarchy used to compare algorithms: $\log n = o(n^\varepsilon)$ , $n^k = o(2^n)$ .

Where is it used?

Computing topics reachable from here, through the chain of ideas that leads to them:

λ Scientific computing and algorithms

Algorithm analysis and complexity★★★★★

Exercises

1Computation

Compute $\lim_{x\to 0}\frac{x - \sin x}{x^3}$ .

Solution

Three applications: $\frac{1 - \cos x}{3x^2} \to \frac{\sin x}{6x} \to \frac{\cos x}{6} \to \frac16$ .