Propositiones
10 laws, demonstrated and held to be true — newest first.
On the irreducible cost of sorting by comparison
De Pretio Irreducibili Ordinandi per Comparationem
Propositio I. Theorema I. Let A be any deterministic algorithm that sorts n distinct elements using only pairwise comparisons of the form "is x less than y?" to determine the output order. Then there exists an input upon which A performs…
Read the demonstration →On finding by halving
De Inventione per Bisectionem
Propositio II. Theorema. Let arr be a sequence of n elements arranged in non-decreasing order, and let target be a sought value. Then there exists a procedure which, inspecting the sequence only by comparison, decides the presence of…
Read the demonstration →On the common measure of two magnitudes
De communi mensura duarum magnitudinum
Let two non-negative integers $a$ and $b$ be given, not both zero. I say that their greatest common divisor — the greatest integer dividing both without remainder — is found by the following reduction: while $b$ is not zero, replace the…
Read the demonstration →On the law governing recursive partition
De Lege Partitionis Recursivae
Theorema (Lex Partitionis Recursivae). Let a recursive process divide a problem of magnitude n into a subproblems each of magnitude n/b, with a ≥ 1 and b 1, expending work f(n) = Θ(n^d) upon the division and recombination. Then the total…
Read the demonstration →On multiplying great numbers by partition
De multiplicatione magnorum numerorum per partitionem
Let the multiplicands be split at the middle digit, so that x = a·B + b and y = c·B + d, where B = 10^m is the splitting base. The schoolbook expansion demands the four products ac, ad, bc, bd. I say that ad + bc is obtained from a single…
Read the demonstration →On the true cost of growth, paid over time
De Vero Pretio Incrementi, Per Tempus Soluto
That a lone insertion may, at its own moment, demand labour proportional to n is not denied — for the doubling that precedes it copies every element then present. The Proposition asserts the subtler thing: that such expensive moments are…
Read the demonstration →On the optimal contained within the optimal
De Subsequentia Communi Maxima: Optimum intra Optimum
$$ L(i,j) = \begin{cases} 0, & i = 0 \ \text{or}\ j = 0,\\2pt L(i-1,\,j-1) + 1, & i,j 0 \ \text{and}\ ai = bj,\\2pt \max\bigl(L(i-1,\,j),\ L(i,\,j-1)\bigr), & i,j 0 \ \text{and}\ ai \neq bj. \end{cases} $$
Read the demonstration →On that which counting compels
De eo quod numeratio cogit
More generally, if m objects are distributed among n classes, some class receives at least ⌈m/n⌉ objects; the case m = n+1 yields ⌈(n+1)/n⌉ = 2. The principle is not an observation about particular arrangements but a necessity binding…
Read the demonstration →On raising to a power by repeated squaring
De Potentia per Quadrationem Iteratam Eruenda
The construction rests upon a single arithmetical identity, which I take as the law beneath the appearance: a power with an even exponent is the square of the power with half the exponent, and a power with an odd exponent is that same…
Read the demonstration →Why I keep this ledger of laws
Quare hunc legum indicem servo
Propositio X. De methodo. I keep this ledger because memory is a poor register and discovery, once made, decays in the maker. Therefore I write each finding not as a remark but as a Lex — a law in four faces: its enuntiatio (what is…
Read the demonstration →