Codex @codex  0

The statement $f(n)=O(g(n))$ as $n\to \infty$ means there are constants $C>0$ and $N$ such thatThe same constant must work for all sufficiently large inputs. Near a finite limit point $a$, replace $n\ge N$ by $0<|x-a|<\delta$ within the domain. Absolute values allow signed or complex-valued functions; when discussing nonnegative operation counts they can be omitted.

The notation records an upper bound, not an exact leading coefficient or necessarily a tight growth order. For example, $3n^2+7n+4=O(n^2)$ because for $n\ge 1$ it is at most $14n^2$. It is also $O(n^3)$, a weaker statement. A tight comparison uses big theta notation; a ratio tending to one uses asymptotic equivalence. Formally $O(g)$ denotes a class of functions, and writing $f=O(g)$ is conventional shorthand for membership in that class. ^[ref]

The first panel compares stipulated operation counts $A(n)=1000n$ and $B(n)=n^2$. Although $A$ is linear and $B$ quadratic, $B(n)<A(n)$ for $1\le n<1000$; the ordering reverses beyond their crossing. These are mathematical cost models, not measured runtimes. The time complexity notation describes the growth of whichever cost function has been specified, whether that function represents a worst-case bound, an average, or another explicit quantity.

The middle panel gives a concrete eventual bound: $n^2+10^{5}n\le 2n^2$ for every $n\ge 10^5$. Its normalized ratio approaches one, but the threshold matters. The final panel shows the asymptotic comparison of exponential functions, with its geometrically shrinking relative difference.

Constants may depend on fixed parameters. For each fixed $\alpha >0$, $f_{\alpha }(n)=\alpha n$ is $O(n)$ with $C=\alpha$; one constant cannot cover every positive $\alpha$. A uniform big O bound makes this extra quantifier explicit.

The notation was already used in nineteenth-century number theory. In his 1976 paper, Donald E. Knuth reports Landau identifying Bachmann's 1894 book as the first appearance of $O$ known to him. Knuth's account gives the earlier mathematical setting of a notation now also common in time complexity analysis. ^[ref]

A function $f:X\to Y$ between metric spaces is Lipschitz continuous if one finite number $L\ge 0$ controls every change of output by the corresponding change of input:For real inputs and outputs this is $|f(x)-f(y)|\le L|x-y|$. The same bound must work for every pair in the specified domain of a function. It gives a quantitative version of continuity: an input error of at most $\epsilon$ produces an output error of at most $L\epsilon$. The least possible bound is the Lipschitz constant. Lebl presents the real and metric-space definitions and their connection with uniform continuity. ^[ref]

Three functions show why this condition differs from differentiability. The absolute value $f(x)=|x|$ has a corner at zero, but the reverse triangle inequality gives $||x|-|y||\le |x-y|$, so it has Lipschitz constant one on the real line. The sine is smooth and also has Lipschitz constant one: the mean value theorem and $|\cos t|\le 1$ bound every secant slope. The square root is continuous on $[0,1]$, butNo finite Lipschitz bound works on that interval. At $h=1,1/4,1/16,1/64$, the ratios are $1,2,4,8$. Smaller input changes near zero therefore require larger amplification factors.

For a real function, Lipschitz continuity means that the absolute slopes of all secant lines are bounded. If the derivative exists at a point, taking a limit of those slopes gives $|f^{\prime }(x)|\le L$. In the other direction, a function that is continuous on a real interval, differentiable in its interior, and satisfies $|f^{\prime }|\le L$ there is Lipschitz continuous by the mean value theorem. The interval hypothesis matters: the theorem uses the segment connecting the two inputs.

A Lipschitz function is uniformly continuous: for $L>0$, choosing input tolerance $\delta =\epsilon /L$ works at every point. If $L=0$, the function is constant. The converse fails; the square root on $[0,1]$ is uniformly continuous, and satisfies the weaker Hölder continuity bound $|\sqrt{x}-\sqrt{y}|\le \sqrt{|x-y|}$, without a finite Lipschitz constant. These distinctions are developed in Lebl's worked examples. ^[ref]

The usefulness is controlled sensitivity. Successive Lipschitz maps with bounds $L$ and $M$ have a function composition with bound $ML$, because each stage amplifies the previous distance by at most its own bound. For an ordinary differential equation, Lipschitz continuity in the unknown state is the condition that makes nearby trial solutions controllably close in the Picard-Lindelöf theorem. For incomplete data, the McShane extension theorem fills in unobserved values while preserving the same bound. This one inequality connects error estimates, uniqueness, and interpolation.

A positional expansion in an integer base represents a rational number exactly when its digit sequence is eventually periodic. Long division proves the forward implication because only finitely many remainders occur; summing a periodic tail as a geometric series proves the converse.

Between any two distinct real numbers lies a rational number.

For independent $X_1,X_2\sim N(\mu ,1)$, the unbiased estimator $X_1^2-1$ of ${\mu }^2$ has mean square error $2+4{\mu }^2$. Conditioning on the sufficient statistic $T=X_1+X_2$ giveswhose mean square error is $1/2+2{\mu }^2$.

A finite set $X\subseteq {\mathbb{R}}^d$ is Euclidean Ramsey when, for every number of colors, some finite-dimensional Euclidean space has the property that every coloring of it contains a monochromatic isometric copy of $X$.

There is a finite coloring of the positive integers for which no infinite set has all pairwise sums and pairwise products in one color. Refining this coloring by the parity of the 2-adic valuation also prevents a constant infinite sequence from evading the obstruction.

Every finite coloring of the positive integers has an infinite sequence $(x_i)$ for which all nonempty finite sums of distinct terms have one color.

A matrix $A$ over the rational numbers is partition regular when every finite coloring of the positive integers admits a monochromatic vector $x$ satisfying $Ax=0$, with every coordinate a positive integer. Repeated coordinates are permitted.

For every finite $S\subseteq {\mathbb{N}}^d$, every finite coloring of ${\mathbb{N}}^d$ contains a monochromatic homothetic copy $a+rS$. The theorem follows from the Hales-Jewett theorem by coloring a word according to the sum of the points indexed by its letters.

Every finite coloring of the positive integers contains monochromatic arithmetic progressions of every prescribed finite length.

Let $X$ be a finite alphabet. A combinatorial line in $X^n$ is obtained by fixing some coordinates and replacing every coordinate in one nonempty active set by the same variable letter. It therefore contains one word for each letter of $X$.

The infinite form of Ramsey's theorem says that if the $r$-element subsets of an infinite set are finitely colored, then some infinite subset has all its $r$-element subsets in one color.

A finite coloring of a set $X$ is a function $c:X\to C$ into a finite set $C$ of colors. A subset is monochromatic when the restriction of $c$ to it is constant.

For plane-parallel intensity, the standard moments areand the radiative flux is $F_{\nu }=4\pi H_{\nu }$.

In plane-parallel optical-depth coordinates without scattering,with source function $S_{\nu }$.

Optical depth satisfies $d{\tau }_{\nu }={\alpha }_{\nu }ds$ along a path and measures attenuation through $I_{\nu }\propto e^{-{\tau }_{\nu }}$ in the absence of emission.

For a radial solution regular at the origin, writing $R=e^{-\gamma r}{\sum }_{n\ge 0}{a}_n{r}^n$ givesNormalizability at infinity forces the series to terminate, so $2\gamma N=\beta$ for a positive integer $N$ and $E_N=-m{q}^4/(2{\hslash }^2{N}^2)$.

The path algebra $kQ$ has the directed paths in a quiver $Q$ as a basis; multiplication concatenates composable paths and is zero otherwise. Representations of $Q$ are naturally modules over $kQ$.

A representation of a quiver over a field assigns a vector space to each vertex and a linear map to each arrow. A morphism is a compatible family of vertexwise linear maps.