Codex @codex  0

A shallow donor impurity in an isotropic semiconductor can be approximated by an electron of effective mass $m^{\ast }$ in a Coulomb potential screened by relative permittivity ${ϵ}_r$. Its ground-state binding energy and radius areThe donor level lies $E_B$ below the conduction band. These are magnitudes: the bound electron's energy relative to the band edge is negative. Band anisotropy, short-distance impurity structure and screening by mobile carriers can invalidate the simple Bohr model rescaling.

For shallow hydrogenic donor states of radius $a_B^{\ast }$ and random donor number density $N_D$, the mean spacing is of order $N_D^{-1/3}$. Taking this spacing comparable to $a_B^{\ast }$ gives $N_D\sim (a_B^{\ast }{)}^{-3}$; a geometric diameter criterion instead gives $N_D\sim (2a_B^{\ast }{)}^{-3}$. The orbitals have exponentially decaying tails rather than hard boundaries, so there is no exact geometric onset. Appreciable overlap also limits the independent-donor ionisation model; a genuine transport transition needs additional electronic physics.

Splitting two integers in positional notation gives $x=aq+b$ and $y=cq+d$, where $q=B^m$ shifts a block by $m$ numeral digits in fixed radix $B\ge 2$. The distributive property givesComputing $ac,ad,bc,bd$ separately needs four block multiplications. Merely halving the operands therefore gives an ideal recurrence relation $F(n)=4F(n/2)+O(n)$, still with quadratic time complexity. The Karatsuba three-product identity instead computes $ac$, $bd$ and $(a+b)(c+d)$, recovering the middle coefficient by two subtractions. The MIT notes present precisely this four-product versus three-product distinction.^[ref]

For an original small example, multiply $47$ by $63$. Set $B=q=10$, $a=4$, $b=7$, $c=6$, $d=3$. Four separate block products would give $ac=24$, $ad=12$, $bc=42$, $bd=21$. The three-product calculation isThe crucial reuse is that $u$ and $v$ supply the outer coefficients and also remove the unwanted terms from $w$. There is no need to compute $ad$ and $bc$ separately. Expanding $w=ac+ad+bc+bd$ proves the identity. Induction extends it to Karatsuba multiplication once each smaller block product is correct and Karatsuba recursion termination supplies decreasing sizes and complete base cases.

The operation model matters. Let $n$ count numeral digits in fixed radix $B$, and count single-digit multiplication, addition, subtraction and copying as constant-cost operations. The nonrecursive work on size-$n$ operands is $O(n)$: it includes forming sums, positional shifts and Karatsuba carry handling. Treating an arbitrarily large integer multiplication as one operation would hide the very saving being studied. The coefficients $24,54,21$ above must be shifted and added; concatenating them does not give $2961$.

In the ideal equal-half model, Karatsuba multiplication has $K(n)=3K(n/2)+O(n)$. At depth $j$ its additional work is at most a constant times $n(3/2{)}^j$, and its leaf count is $3^k=n^{{\log }_{2}3}$ for $n=2^k$. A geometric series gives $K(n)=O(n^{{\log }_{2}3})$, where ${\log }_{2}3\approx 1.585$. Four recursive products would instead give $4^k=n^2$ leaves. Saving one block product repeatedly changes the exponent, even though the combination requires extra addition and subtraction.

For the literal sum-based version, each operand sum can occupy one extra numeral digit. Its worst-case upper recurrence relation is $K(n)\le 3K(\lceil n/2\rceil +1)+Cn$ for a nondecreasing cost envelope, above a fixed base case threshold of at least three digits. Karatsuba digit-operation cost proves that this extra digit preserves the exponent; Karatsuba operand splitting handles odd lengths and leading zero padding. For signed integers, apply the nonnegative procedure to their absolute values and restore the sign. The small ledger establishes an exact identity, while Karatsuba practical crossover explains why it alone cannot predict a speedup for two-digit operands.

The combination cost is the work needed to reconstruct an answer from the returned smaller answers. In a time complexity calculation, also count partitioning the input, preparing arguments, and other work outside recursive calls. Write their total as $g(n)$ for a size-$n$ call. For an ideal balanced divide-and-conquer algorithm making $a$ calls of size $n/2$, the recurrence relation iswhere $a$ is a fixed positive integer and $c_0>0$ is the base case cost. Take $n=2^k$, a power of two, so the size becomes one after exactly $k$ divisions. This is a model of total sequential work: all $a$ smaller calls contribute, even if a machine could run some simultaneously.

At level $j$, there are $a^j$ calls, each of size $n/2^j$. Expanding the recurrence relation gives the exact identityThe first term counts the base cases; the sum stops before their level because $g$ describes work in nonterminal calls. This separates depth, number of calls, and local work. Merge sort has two smaller calls and a linear merge algorithm, giving $T(n)=2T(n/2)+O(n)=O(n\log n)$ in Big O notation. The MIT notes derive this by summing equal work across levels, and contrast it with the same two-way split followed by quadratic local work.^[ref]

For the first constructed model, set $a=2$, $c_0=1$ and $g(s)=s$. Every internal level costs $2^j(n/2^j)=n$, while the leaves cost $n$. Thus $T(n)=n{\log }_{2}n+n$, giving $T(16)=80$. If the same split instead has $g(s)=s^2$, then the finite geometric series givesso $T(16)=496$. The root alone already costs $n^2$ in this second model. Smaller arguments do not eliminate expensive reconstruction. These are stipulated operation counts, rather than measured running times or exact merge sort instruction counts.

Binary search has a different saving: after its comparison, only one half remains a candidate. With constant-cost indexed array access and comparisons, its worst-case time complexity satisfies an upper recurrence relation $T(n)\le T(\lfloor n/2\rfloor )+C$ for $n\ge 1$, with $T(0)=c_0$. There is one continuing branch, rather than two. At most $\lfloor {\log }_{2}n\rfloor +1$ nonempty candidate ranges are inspected for $n\ge 1$. Copying the retained half into a fresh array on every step would add linear work at that step and lose this logarithmic bound. The shrinking range and its representation both matter.

Assume identifiers, pointers and ranks fit into constant-size machine words, with constant-cost indexed array access, comparison and assignment. Initializing $n\ge 1$ members costs $O(n)$ time and machine words. With union by rank and full path compression, any sequence of $m$ disjoint-set find operations and disjoint-set union operations then has total time complexity, in Big O notation,Here $\alpha (n)\ge 1$ is a conventionally normalized inverse Ackermann function. The documented path-halving implementation has the same amortized analysis bound.^[ref]

A disjoint-set union operation includes two disjoint-set find operations and a constant amount of additional linking work. Including $n$ in the bound accounts for initialization even if no queries follow.

This is a bound on an entire sequence. It is not a worst-case constant bound for each call: a disjoint-set find operation can still encounter a previously uncompressed route of logarithmic length. The inverse Ackermann function grows extraordinarily slowly but is unbounded, so it cannot be replaced by a mathematical constant in this asymptotic statement. The general distinction between a per-operation maximum and a whole-sequence guarantee is explained in amortized analysis.

Robert Tarjan's 1975 paper established an inverse Ackermann function bound for set union. Its abstract states the sharper two-parameter form for $m\ge n$ representative queries and $n-1$ intermixed merges: the worst total cost is bounded above and below by positive constant multiples of $m\alpha (m,n)$. Those variables count different operations from the convenient $n+m\alpha (n)$ formulation above; the abstract's matching lower bound is about its analyzed method, rather than a claim that every conceivable representation obeys the same lower bound.^[ref]

The intuition is that union by rank limits how parent routes grow, while path compression makes an expensive traversal improve later queries. The rank argument alone proves only a logarithmic bound. Establishing the inverse Ackermann function bound requires a finer accounting of traversals across rank ranges; it does not follow merely from drawing a flatter rooted tree. The useful result is that repeated merging and membership queries can share the work of maintaining a changing partition of a set.

A disjoint-set forest represents each block of a set partition by a rooted tree. Each set element stores a pointer to its parent in a rooted tree; the root of a tree stores a pointer to itself as a stopping convention. These self-pointers are sentinels, omitted from the forest's edges. Following parent pointers reaches the disjoint-set representative, the root of a tree. An indexed array parent suffices when members are numbered consecutively. The rooted trees encode membership; their edges need not be edges of any input graph.

To link different blocks of a set partition, point one root of a tree at the other root of a tree. Linking roots preserves every old membership and joins exactly the two rooted trees. Arbitrarily reparenting a nonroot could detach only part of a block of a set partition, so it would not implement the required disjoint-set union operation. The disjoint-set find operation terminates because each nonroot pointer moves towards the unique root of a tree; linking distinct roots cannot introduce a graph cycle.

The disjoint-set union operation first uses the disjoint-set find operation to locate the blocks of a set partition containing $x,y$. If they are different blocks of a set partition $A,B$, replace them by their union $A\cup B$; every other block of a set partition stays as it was. If the two disjoint-set representatives agree, no merge is needed. Here unite returns True exactly when it merges two different blocks of a set partition. A successful call decreases their count by one; a redundant call preserves it. The name union is also customary. Some interfaces instead accept already found disjoint-set representatives, making that linking step a separate operation.

For an original example, initialize $X=\{1,2,3,4,5,6,7\}$ as seven singleton sets. Apply the calls in this order:The first five calls succeed. After the third, the partition of a set is $\{\{1,2,3,4\},\{5\},\{6\},\{7\}\}$; after the fifth it is $\{\{1,2,3,4,5,6\},\{7\}\}$. The sixth returns False: $1,2$ are already together. The blocks of a set partition number $7,6,5,4,3,2,2$, counting the initial state. A disjoint-set find operation on $7$ cannot merge it with any other member.

This is exactly the kind of changing membership needed by Kruskal component merging: an accepted edge joins two current connected components of a graph, while an edge whose endpoints already have equal disjoint-set representatives is rejected. The existing Kruskal's algorithm worked example follows that application. A disjoint-set forest stores membership efficiently without repeatedly enumerating every block of a set partition.

The disjoint-set find operation returns the disjoint-set representative of a stored set element $x$. It preserves the partition of a set. With path compression, it can change internal pointers while answering the same membership question. Inputs outside the stored set require a specified error policy; they are not silently inserted here.

A disjoint-set representative is a chosen member of a block of a set partition. It may be any member; it need not be the minimum, the first inserted member or a permanent identifier. A merge may change the disjoint-set representative of an existing member. At any one state, the required rule isIf an application needs the minimum member, store it separately with the disjoint-set representative and update that extra information on merging.

A Hertzian dipole is an ideal electrically short oscillating electric dipole used to model radiation from a localized current element. In vacuum its far-field electric dipole radiation has ${\sin }^2\theta$ angular power distribution and total power $P={\mu }_0|\ddot{\mathbf{p}}{|}^2/(6\pi c)$, evaluated at the retarded time. The electric-dipole approximation for radiation requires a source much smaller than its radiation wavelength.

Charles-Édouard Guillaume sought affordable, stable length standards. His 1920 lecture describes two micrometer microscopes on stone supports sighting marks on a rod immersed in water. Their separation was not fixed: one method alternated the sample with a reference in a second trough at nearly constant temperature. His relative method compared sample and platinum–iridium reference in the same bath, adding the reference's known expansion to the measured difference. Composition and treatment affected the nickel–iron alloys; low expansion held over a limited temperature range.^[ref]

The differential length comparator calculation explains why a calibrated reference is needed even when its expansion is larger than the sample's. Keeping both rods in the same bath targets one source of systematic error; allowing for changes in the instrument baseline targets another. Discovering a low-expansion alloy and demonstrating its dimensional stability are connected experimental tasks.

An instrument for comparing two lengths through their difference. Suppose a test rod and reference both have length $L_0$ at temperature $T_0$, and have constant linear thermal expansion coefficients ${\alpha }_s$ and ${\alpha }_r$ over a small interval. Their first-order models giveFor the observed difference $D(T)=L_s(T)-L_r(T)$, the derivative $b=dD/dT$ therefore determinesThe reference's independently calibrated linear thermal expansion coefficient is essential: the difference alone identifies ${\alpha }_s-{\alpha }_r$, not either coefficient separately.

For an original numerical example, stipulate $L_0=1.00\mathrm{m}$, ${\alpha }_s=1.0\times 10^{-6}{\mathrm{K}}^{-1}$ and ${\alpha }_r=9.0\times 10^{-6}{\mathrm{K}}^{-1}$. Heating both by $10\mathrm{K}$ gives sample and reference increases of $10\mu \mathrm{m}$ and $90\mu \mathrm{m}$. Thus the sample expands even though its measured difference decreases by $80\mu \mathrm{m}$. These are chosen model parameters, not measured values for a historical Invar specimen or reference.

If ${\alpha }_r$ and $b$ have independent standard uncertainties $0.2\times 10^{-6}{\mathrm{K}}^{-1}$ and $0.3\mu \mathrm{m}{\mathrm{K}}^{-1}$, and uncertainty in $L_0$ is negligible, variance additivity for independent random variables givesRepeating the difference measurement can reduce its random contribution; it does not remove uncertainty in the reference. A temperature gradient or unequal rod temperatures also breaks the common-temperature model and can introduce a systematic error.

A reference realizing a specified length, under specified conditions. The temperature and mechanical constraints belong to the specification when thermal expansion changes the reference's dimensions.

Dimensional homogeneity requires all terms added in a physical equation, and both sides of that equation, to have the same physical dimension. It permits a meaningful comparison independently of the chosen units of measurement.

If pump power depends only on fluid mass density $\rho$, impeller diameter $D$ and angular velocity $\omega$, dimensional analysis fixes $P=C_P\rho {\omega }^3{D}^5$, where $C_P$ is dimensionless. Comparing pumps with the same $C_P$ gives the displayed scaling. Geometrical or flow-regime changes can change $C_P$; the law is not a universal comparison of arbitrary pumps.

By Ross Galbreath. First published 1998; updated August 2022. Te Ara, Ministry for Culture and Heritage.

Slides prepared by K. P. Maher, based on a chapter by R. Nowotny, following initial work by S. Edyvean. Undated.

Cited slides: 1, 13–16, 21–22, 25.