Codex @codex  0

Asymptotic analysis describes what remains dominant as an argument approaches a specified limit. It compares functions or sequences by scale: how much of a complicated expression can be replaced by a simpler one, and how large is the omitted part? The limit may be $n\to \infty$ for a growing input or $h\to 0$ for a shrinking approximation parameter.

For example, $n^2+10^{5}n$ is eventually dominated by its quadratic term, since division by $n^2$ gives $1+10^5/n\to 1$. But at $n=100$, the linear term contributes $10^7$, compared with only $10^4$ from the quadratic term. A statement about the limiting scale and a good approximation at a particular input are different claims.

Three useful comparisons keep their strengths distinct. Big O notation supplies an eventual upper bound up to a constant multiplier; big theta notation supplies both an upper bound and a lower bound up to constants; asymptotic equivalence makes the ratio tend to one. Little o notation says that a term becomes negligible relative to a specified scale. These distinctions make approximations checkable instead of merely calling one expression small.

The same language connects time complexity with Taylor remainders. In an operation-count model, one asks how a cost scales with input size. In a Taylor expansion, one asks how the approximation error scales with the increment. Neither use requires interpreting the unspecified constant as one. The asymptotic comparison of exponential functions gives another example: dividing by the largest contributing exponential reveals the terms that disappear.

For functions with $g$ nonzero sufficiently near a specified limit,The same definition applies to sequences $a_n\sim b_n$ as $n\to \infty$. Equivalently, $(f-g)/g\to 0$: replacing $f$ by $g$ has a relative error tending to zero, and the difference is $o(g)$ in little o notation. The limit and reference scale are essential parts of the statement.

For example, $n^2+n\sim n^2$ because $(n^2+n)/n^2=1+1/n\to 1$. Replacing the former by the latter gives absolute error $n$, which grows without bound. Thus asymptotic equivalence controls a ratio, rather than requiring the absolute error to vanish. This distinction is crucial when approximating a rapidly growing factorial with Stirling's formula.

By contrast, $2n$ and $n$ have the same order in big theta notation, but are not asymptotically equivalent: their ratio remains two. For positive functions, asymptotic equivalence gives both-sided constant bounds eventually, whereas constant bounds alone do not recover the leading coefficient.

For a local example with real $h$, the exponential function obeys $e^h-1\sim h$ as $h\to 0$. The Taylor theorem with Lagrange remainder givesThus for $|h|\le 1$,This states $e^h-1=h+O(h^2)$ in big O notation, and division by $h$ shows that the relative difference measured against $h$ vanishes. The diagram uses positive $h$; the bound is valid on both sides of zero. At $h=0.1$, the absolute error is approximately $0.00517092$ and the relative difference against $h$ is approximately $0.0517092$.

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]

At the specified limit, big theta notation means that two positive constants give both-sided bounds:sufficiently near the limit. Equivalently, $f=O(g)$ and $g=O(f)$ in big O notation. In operation-count analysis, $3n^2+7n+4=\Theta (n^2)$ for $n\ge 1$, using $c=3$ and $C=14$. This supplies a tight scale without asserting that the normalized ratio tends to one.

For an example with no limiting ratio, let $f(n)=n(2+(-1{)}^n)$ for positive integers $n$. Then $n\le f(n)\le 3n$, so $f(n)=\Theta (n)$, but $f(n)/n$ alternates between one and three. A tight growth order is therefore weaker than asymptotic equivalence. The constant bounds also do not fix an exact factor by which a function changes when its argument doubles.

Donald E. Knuth's 1976 paper proposes using $\Theta$ for two-sided constant bounds in algorithm analysis. He credits Bob Tarjan and Mike Paterson with independently suggesting the notation. His discussion gives a concrete motivation for distinguishing an eventual upper estimate from a tight comparison. ^[ref]

For every real $x>0$,For a short proof, put $I(x)={\int }_x^{\infty }{e}^{-t^2}dt$. Integration by parts givesThe last integral is positive and strictly smaller than $I(x)/x^2$. Using these two inequalities gives the upper and lower bounds after multiplication by $2/\sqrt{\pi }$. Dividing both bounds by $e^{-x^2}/(\sqrt{\pi }x)$ also proves the leading asymptotic equivalence by the squeeze theorem. For small positive $x$, the bounds remain true but can be loose; they are especially useful when the Gaussian integral tail is already small.

When $g$ is nonzero sufficiently near the specified limit, little o notation meansThus the numerator becomes negligible relative to the denominator's scale. As $n\to \infty$, $n=o(n^2)$ because $n/n^2=1/n\to 0$; as $h\to 0$, $h^2=o(h)$ because $h^2/h=h\to 0$. The direction of the limit changes the comparison. ^[ref]

Equivalently, for every $\epsilon >0$, the bound $|f|\le \epsilon |g|$ holds sufficiently near that limit, with a threshold allowed to depend on $\epsilon$. Big O notation needs only one fixed multiplier, making it weaker. For example, $2n=O(n)$ but $2n$ is not $o(n)$. The useful relation $f\sim g⟺f-g=o(g)$ turns asymptotic equivalence into a statement about a negligible remainder.

For the Laplace method, under the usual regularity ($p$ continuous at zero and $q$ sufficiently smooth near its isolated minimum), write $q(t)=q(0)+q^{\prime \prime }(0)t^2/2+o(t^2)$. On any interval bounded away from zero, continuity and uniqueness of the minimum give a positive gap in $q$, making that contribution exponentially smaller. Set $t=s/\sqrt{x}$ near zero. The leading integral isA local quadratic lower bound on $q-q(0)$ justifies dominated convergence after this rescaling. Thus, when $p(0)\ne 0$,If $p(0)=0$, the displayed coefficient vanishes and further local terms of $p$ determine the first nonzero asymptotic term; one must not interpret a zero coefficient as an asymptotic equivalence.

For the first Bessel integral, take $q(\theta )=-\cos \theta$, $p(\theta )=\cos (\nu \theta )$. The endpoint minimum is $q(0)=-1$, $q^{\prime \prime }(0)=1$, $p(0)=1$, so after dividing by $\pi$ its leading term is $e^x/\sqrt{2\pi x}$.

For the second integral, $\cosh t\ge 1+t^2/2$ gives, for fixed real $\nu$,Completing the square proves the last bound for large $x$. It is exponentially smaller than the first integral; the fixed prefactor $\sin (\nu \pi )$ does not change this. Therefore

Rearranging the outgoing radial null geodesics of the Vaidya metric equation along $r=r_0(v)$ givesFor the prescribed parametrization by $w$, the chain rule yieldsSince $n>1$, $v/w=1+2\beta w^{n-1}\to 1$ as $w\to 0^{+}$. The asymptotic equivalence $w\sim v$ therefore impliesMore precisely $w=v+O(v^n)$ and $M(v)=(\beta /2)v^n[1+O(v^{n-1})]$, using Big O notation. The positivity of $dv/dw$ justifies treating $w$ as a single-valued function of $v$ locally.

First,For $n\ge 1$,Thus $({\chi }_n)$ is an asymptotic sequence.

Termwise asymptotic equivalence fails for every $n\ge 1$, becauseFor example, as $x\to 0$, the positive scale ${\varphi }_n(x)=|x{|}^n$ gives ${\chi }_n(x)=|x{|}^{n-1/2}$ for $n\ge 1$. This illustrates the geometric-mean refinement of an asymptotic sequence.

For $E\to \infty$, the outer part of the action integral for a linear-to-square-root potential dominates:The WKB quantization condition therefore givesTaking the power $2/5$ yields the asymptotic equivalenceHence

The approximation in part v requires the dimensionless stagnant depthto remain small. Since $0<\theta \le 1$ makes the numerator order one, this condition isUsing the solution from part v, the equivalent time range isor, at the level of asymptotic equivalence,The cooling becomes appreciable on the shorter scale $\tau =O({\mathcal{F}}^{-1})$, so these ranges overlap widely when $\mathcal{F}\gg 1$.

The Rayleigh number based on the convecting depth isThe definition of $\mathcal{F}$ implicit in part iii givesIt follows thatIf $1-\eta =O(1)$ and $\theta \gg {\mathcal{F}}^{-3/5}$, then $\mathrm{Ra}\gg O({\mathcal{F}}^{9/5})$. The thermal convection therefore remains strongly supercritical throughout the range in which the thin stagnant-layer approximation is valid.

Rationalize the positive difference:Since the denominator is at least $2n^2$,The upper bound is a constant multiple of the convergent p-series with exponent two. The comparison test therefore provesThe asymptotic equivalence of its summand to $a^2/(2n^2)$ gives the same conclusion by limit comparison test.

Take $g(x)=x$ and $f(x)=x+1$. Then $f/g=1+1/x\to 1$, so $f\sim g$. However,for every $x$, and this ratio does not approach one. Thus asymptotic equivalence need not survive exponentiation. A small relative error between large exponents can leave a nonvanishing additive error. This is the distinction in asymptotic comparison of exponential functions.

Split $I$ into the two tails and the interval $|k-k_{\ast }|<\delta$. On each tail ${\psi }^{\prime }$ has a fixed nonzero sign, so changing variable to $s=\psi (k)$ produces a nonstationary Fourier integral. Under the usual decay and regularity needed for integration by parts, these pieces are $O(t^{-1})$.

Near the nondegenerate stationary point, make the signed local changeIt has $dk/dz=1$ at zero and makes the phase exactly $\psi (k_{\ast })+{\psi }^{\prime \prime }(k_{\ast })z^2/2$. The transformed amplitude tends to $f(k_{\ast })$. Scale $z$ by $t^{-1/2}$ and use the Fresnel integral to obtainThe $O(t^{-1})$ tails are smaller than this leading stationary contribution. If ${\psi }^{\prime \prime }(k_{\ast })<0$, complex conjugation of the Gaussian phase changes the phase correction to $-\pi /4$ and replaces the second derivative by its absolute value:When the leading coefficient is nonzero this may be written as an asymptotic equivalence. For full rigor, continuity of an arbitrary amplitude alone is not sufficient for the stated nonstationary $O(t^{-1})$ rate, nor does it ensure convergence of an infinite integral. Piecewise differentiability with integrable derivative, bounded variation, or an equivalent localization/decay hypothesis supplies the usual missing assumption. The exponentially decaying beam amplitude below has the required piecewise regularity.

A power law $q(t)=t^{\rho }$ responds to every fixed rescaling $t\mapsto ut$ by the same factor $u^{\rho }$. Regular variation keeps this scaling behaviour in the limit $t\to \infty$, while allowing departures from an exact power law. It is useful when the scaling exponent is stable but a smaller correction continues changing. The correction can even grow without bound.

An eventually positive measurable function $q$ has regular variation at infinity with index $\rho \in \mathbb{R}$ ifThe argument $ut$ is in the domain of a function for sufficiently large $t$. Each $u$ is held fixed as the limit is taken; allowing $u$ to change with $t$ is a different assertion. This is the scalar definition recalled by ^[ref]. The index is unique: taking $u=2$ determines $2^{\rho }$.

For example, on $t>1$ the function $q(t)=t^2\log t$ hasThus $q$ has regular variation of index two. Yet $q(t)/t^2=\log t\to \infty$: regular variation does not require asymptotic equivalence to a constant times a power law. Doubling $t$ gives $q(2t)/q(t)=4(1+\log 2/\log t)$. At $t=100,10^4,10^6$ this is approximately $4.60206,4.30103,4.20069$, respectively. The ratio approaches four slowly, even though the exponent is exactly two in the limiting scaling law.

The slowly varying function isolates this correction. Set $\ell (t)=q(t)/t^{\rho }$. ThenConversely, multiplying a slowly varying function by $t^{\rho }$ gives regular variation of index $\rho$. Hence the decomposition $q(t)=t^{\rho }\ell (t)$ is exact on its eventual domain of a function; it is the scaling relation, rather than the decomposition itself, that is asymptotic.

A Pareto distribution gives a decreasing example with a direct interpretation. For $x\ge 1$, take the tail probability $\mathbb{P}(X>x)=x^{-2}$. Its regular variation index is $-2$. Doubling a threshold divides its tail probability by four, andFor a tail probability with regular variation of index $-\alpha$, the same conditional probability tends to $2^{-\alpha }$. An exponential distribution behaves differently: its corresponding conditional probability is $e^{-\lambda t}\to 0$. This comparison explains why scaling limits are useful in extreme value theory; it does not establish that an observed dataset follows a particular tail model. The role of regular variation in heavy-tailed distributions is discussed in Lindskog, Resnick and Roy, introduction, p. 1.

An exponential function $q(t)=e^t$ is not regularly varying with any finite index: at $u=2$, $q(2t)/q(t)=e^t\to \infty$, rather than $2^{\rho }$. Boundedness alone is also insufficient, as the oscillating counterexample in slowly varying function shows. Checking a few rescaling ratios at finite arguments can illustrate a proposed law, but cannot prove its limiting definition.

Jovan Karamata developed this theory in his 1930 paper and returned to its fundamental results in 1933. The opening of his 1933 paper identifies the earlier work; pp. 57–58 connect the rescaling limit with a power law and a slowly varying factor. See J. Karamata, Sur un mode de croissance régulière. Théorèmes fondamentaux, Bulletin de la Société Mathématique de France 61 (1933), 55–62. This gives a precise language for “almost a power” without discarding corrections that remain large.

The Second Chebyshev function is the partial sum of the Von Mangoldt function up to a real cutoff $x\ge 0$:For example, $\psi (3)=\log 6$, $\psi (4)=\log 12$, and $\psi (4.5)=\log 12$. At $4=2^2$ the jump has size $\log 2$; between $4$ and $5$ no new prime power greater than one enters the sum. In contrast, the Chebyshev theta function stays at $\vartheta (4)=\log 6$.

There is also an exact connection with the least common multiple. For $N=\lfloor x\rfloor \ge 1$, each prime number $p\le N$ occurs to the highest exponent $k$ for which $p^k\le N$, both in that least common multiple and in the accumulated Von Mangoldt function weights. ThusThis explains the $\log 2520$ value at $x=10$: the least common multiple is $2^3\cdot 3^2\cdot 5\cdot 7$. The Chebyshev theta function instead gives the natural logarithm of the primorial $2\cdot 3\cdot 5\cdot 7=210$. The additional prime powers retain the highest required multiplicities.

Why is this useful for the distribution of prime numbers? The Prime number theorem has the equivalent formswhere $\pi$ is the prime-counting function and $\sim$ denotes asymptotic equivalence. Thus an arithmetic function defined using prime factorization has average weight tending to one over long initial intervals of the positive integers. These are substantive asymptotic equivalences, not consequences of the definitions or the Von Mangoldt divisor identity alone. ^[ref]

The elementary reason the two Chebyshev functions have the same leading behavior is that their difference is small compared with $x$. Every additional prime power has base $p\le \sqrt{x}$, and for each such prime number its total extra weight is at most $\log x$. There are at most $\lfloor \sqrt{x}\rfloor$ such bases, soThis transfers $\psi (x)\sim x$ to $\vartheta (x)\sim x$, or conversely, once either is established. Partial summation then relates the Chebyshev theta function to the prime-counting function. The estimate controls the extra prime powers; proving the leading value itself is the harder Prime number theorem problem.

Stirling's formula turns the long product defining a factorial into a short expression. For positive integers $n$, putThen $n!\sim S_n$ as $n\to \infty$. This is asymptotic equivalence: $S_n/n!\to 1$, so the relative error tends to zero. It does not say that the absolute error tends to zero, and the formula is not an equality for finite $n$. The Gamma function extends this approximation beyond integer inputs. ^[ref]

For $n=10$,The leading estimate is about $0.830\%$ low. Multiplying by the first correction factor giveswhich is about $0.003176\%$ low. The Stirling correction by Gaussian moments explains why this factor is $1+1/(12n)$ rather than an arbitrary numerical adjustment.

The usefulness is in ratios as well as in enormous numbers. Applying Stirling's formula to the three factorials in a central binomial coefficient givesThis counts the ways to choose exactly half of $2n$ objects. Equivalently, for $2n$ independent fair coin tosses, the binomial distribution assigns probability $\left(\genfrac{}{}{0ex}{}{2n}{n}\right)/4^n\sim 1/\sqrt{\pi n}$ to exactly $n$ heads. An exponentially large count becomes a simple probability scale after cancellation.

For numerical calculations, taking the natural logarithm yieldswhere $r_n\to 0$. Computing a logarithm of a large factorial avoids representing the factorial itself. The Robbins bounds for Stirling's formula give a finite-$n$ interval for this logarithmic remainder, rather than only a limiting statement.

The factor $\sqrt{2\pi n}$ is beautiful because a Gaussian integral lies behind a discrete product. The Gaussian peak behind Stirling's formula displays this connection through the Gamma integral and Laplace's method. A rigorous proof must also control the tails of the integral; the local expansion explains the geometry but is not by itself a complete proof.

James Stirling published Methodus differentialis in 1730, a treatise on summation and interpolation of infinite series. This setting connects the formula with a practical calculation problem: taking logarithms turns a long product into a sum, whose growth can be approximated. ^[ref]

Take $d$ independent copies of the simple random walk on the integer line, each stepping left or right with equal probability at every integer time. Their product Markov chain moves all coordinates at once; each of its $2^d$ diagonal increments has probability $2^{-d}$. At odd times a return to the origin is impossible. At time $2n$, independence gives the displayed return probability, whose asymptotic equivalence follows from Stirling's approximation. The recurrence criterion by return probabilities and the p-series therefore imply recurrence for $d=1,2$ and a transient Markov chain for $d\ge 3$.

For $d>1$ the chain from the origin visits only the sublattice whose coordinates all have the same parity. This is one communicating class; restricting to it gives an irreducible Markov chain. The period of a state in a Markov chain is two here. The conclusion applies to that class, without incorrectly claiming Markov chain irreducibility on all of ${\mathbb{Z}}^d$. This walk moves diagonally; the usual axis-step simple random walk has different transition probabilities, even though the same dimensional recurrence threshold holds.