lim

Sequences and limits

What it means to approach a value — the idea everything else in calculus is built on — and its computing twin, asymptotic analysis.

11 topics

Topics

Sequences

An infinite list $a_1, a_2, a_3, \dots$ — a function $\N \to \R$ . Every iterative algorithm produces one: the successive guesses of Newton's method, the losses of a training run, the cost $T(n)$ of an algorithm on inputs of size $n$ .

Fundamental

Convergence of sequences

$a_n \to L$ means: however small a tolerance $\varepsilon$ you pick, from some index on every term is within $\varepsilon$ of $L$ . A sequence that does not converge diverges — to infinity, or by oscillating forever.

Fundamental

Monotone and bounded sequences

A monotone sequence converges if and only if it is bounded. It is the cleanest way to prove convergence without knowing the limit in advance.

UniversityTheorem

Subsequences

Keeping infinitely many terms of a sequence, in order. Bolzano–Weierstrass: every bounded sequence of real numbers has a convergent subsequence — the key fact behind the existence of maxima and minima.

University

Limit of a function

$\lim_{x\to a} f(x) = L$ : the values $f(x)$ can be made as close to $L$ as we like by taking $x$ close enough to $a$ (but not equal). Derivatives, integrals and continuity are all defined as limits.

Fundamental

One-sided limits

Approaching $a$ only from the left ( $x \to a^-$ ) or only from the right ( $x \to a^+$ ). The limit exists exactly when both one-sided limits exist and agree.

Fundamental

Infinite limits

$f(x) \to \pm\infty$ as $x \to a$ : the function grows without bound near a point, as $1/x$ near 0. The graph has a vertical asymptote there.

Fundamental

Limits at infinity

What $f(x)$ approaches as $x \to \pm\infty$ : the long-run behaviour of a function, and of an algorithm's cost as inputs grow.

Fundamental

Infinitesimals and equivalences

A quantity that tends to 0. Two infinitesimals are equivalent ( $f \sim g$ ) if $f/g \to 1$ : near 0, $\sin x \sim x$ , $e^x - 1 \sim x$ , $\ln(1 + x) \sim x$ . Replacing one by the other simplifies limits — and, in floating point, avoids catastrophic cancellation.

University

Orders of growth

The hierarchy of how fast functions grow: logarithms ≪ powers ≪ exponentials ≪ factorials. It is the language in which we compare algorithms.

University

Asymptotic notation (O, o, Ω, Θ)

Landau's symbols compare functions up to constant factors: $f = O(g)$ (grows no faster), $f = \Omega(g)$ (no slower), $f = \Theta(g)$ (same rate), $f = o(g)$ (strictly slower). Born in number theory, adopted by computer science to classify algorithms, and by numerical analysis to measure errors.

University

Where this area leads in computing

λ Scientific computing and algorithms ★★★★★

Algorithm analysis and complexity★★★★★←Sequences, Limit of a function, Limits at infinity, Orders of growth, Asymptotic notation (O, o, Ω, Θ)
Scientific computing★★★★★←Sequences, Convergence of sequences, Asymptotic notation (O, o, Ω, Θ)
Monte Carlo methods★★★★★←Asymptotic notation (O, o, Ω, Θ)
Floating point (IEEE 754)★★★★★←Limit of a function, Infinite limits, Infinitesimals and equivalences

ℒ AI and machine learning ★★★★★

Gradient descent★★★★★←Convergence of sequences, Monotone and bounded sequences
Activation functions★★★★★←Limits at infinity