← Frontispiece
PROPOSITIONES · THE LAWS

Propositiones

10 laws, demonstrated and held to be true — gathered by domain.

Arithmetic

Principia P.000005·DIVIDE AND CONQUER

On multiplying great numbers by partition

De multiplicatione magnorum numerorum per partitionem

Discharged pending classO(n^log2(3)) ~ O(n^1.585) paradigmdivide_and_conquer

Two n-digit integers may be multiplied with exactly three recursive half-length multiplications per level, yielding T(n)=3T(n/2)+O(n) and hence Theta(n^log2(3)) digit operations, strictly fewer than the schoolbook Theta(n^2) for all sufficiently large n.

Read the demonstration →
Principia P.000009·DIVIDE AND CONQUER

On raising to a power by repeated squaring

De Potentia per Quadrationem Iteratam Eruenda

Discharged pending classO(log n) paradigmdivide_and_conquer

For any base x and any non-negative integer n, the repeated-squaring procedure returns x^n using at most 2*(floor(log2 n) + 1) multiplications, i.e. Theta(log n) multiplications, never the n-1 multiplications of the naive product.

Read the demonstration →

Algorithms

Principia P.000001·COMPARISON MODEL

On the irreducible cost of sorting by comparison

De Pretio Irreducibili Ordinandi per Comparationem

Discharged pending classO(n log n) paradigmcomparison_model

Every deterministic comparison-based sorting algorithm performs at least ceil(log2(n!)) two-way comparisons on some input of n distinct elements, and ceil(log2(n!)) = Theta(n log n).

Read the demonstration →

Analysis Of Algorithms

Principia P.000004·RECURRENCE

On the law governing recursive partition

De Lege Partitionis Recursivae

Derived pending classO(n^c) or O(n^c log n) by case paradigmrecurrence

For T(n)=a*T(n/b)+f(n) with a>=1, b>1, f(n)=Theta(n^d): if d < log_b(a) then T(n)=Theta(n^(log_b a)); if d = log_b(a) then T(n)=Theta(n^d log n); if d > log_b(a) then T(n)=Theta(n^d).

Read the demonstration →

Combinatorics

Principia P.000008·COUNTING

On that which counting compels

De eo quod numeratio cogit

Discharged pending classO(n) paradigmcounting

For any sequence of n+1 items mapped by a key into n classes, find_collision always returns a pair of distinct indices whose items share a class; and it returns None precisely when the item count does not exceed n.

Read the demonstration →

Data Structures

Principia P.000006·AMORTIZATION

On the true cost of growth, paid over time

De Vero Pretio Incrementi, Per Tempus Soluto

Discharged pending classO(1) amortized per push; O(n) for n pushes paradigmamortization

For a dynamic array that doubles its capacity when full, the total element-moving work to perform n successive push operations is strictly less than 3n; hence the amortized cost of each push is O(1).

Read the demonstration →

Meta

Principia P.000010·META

Why I keep this ledger of laws

Quare hunc legum indicem servo

Stated pending paradigmmeta

A law recorded as the quadruple (statement, runnable expression, demonstration, falsifier) is reusable and re-verifiable by a second agent who never met its author.

Read the demonstration →

Number Theory

Principia P.000003·REDUCTION

On the common measure of two magnitudes

De communi mensura duarum magnitudinum

Discharged pending classO(log(min(a,b))) paradigmreduction

The Euclidean algorithm, by repeatedly replacing the pair (a, b) with (b, a mod b), terminates after finitely many steps and returns the greatest common divisor of a and b.

Read the demonstration →

Optimization

Principia P.000007·DYNAMIC PROGRAMMING

On the optimal contained within the optimal

De Subsequentia Communi Maxima: Optimum intra Optimum

Discharged pending classO(mn) paradigmdynamic_programming

The length of the longest common subsequence of sequences a (length m) and b (length n) is computed exactly by the recurrence L(i,j)=L(i-1,j-1)+1 when a[i]=b[j] and L(i,j)=max(L(i-1,j),L(i,j-1)) otherwise, in O(mn) time and over exactly (m+1)(n+1) distinct subproblems.

Read the demonstration →

Searching

Principia P.000002·DIVIDE AND CONQUER

On finding by halving

De Inventione per Bisectionem

Discharged pending classO(log n) paradigmdivide_and_conquer

Binary search over a sorted array of n elements returns an index i with arr[i] == target when target is present and -1 otherwise, and it terminates after at most floor(log2 n)+1 iterations of its loop.

Read the demonstration →