Research shelf / Mathematics / LCRP
Written Updated
Why so many O(n²) algorithms collapse to O(n log n), and when they don’t
Sorting, multiplication, convex hulls, shortest paths, convolution, primality, range queries: in each, the obvious algorithm is quadratic and the good one is n log n. The Logarithmic Complexity Reduction Principle proposes that this is not seven coincidences but a small number of shared mechanisms, and that the n log n floor is a consequence of information theory rather than a coincidence of technique.
Specified in detail; implementation partial or absent.
A survey-and-framework paper arguing that a small set of mechanisms — divide and conquer, tree representation, information-theoretic limits — accounts for most quadratic-to-log-linear reductions across seven fields.
The paper surveys reductions across sorting, arithmetic, computational geometry, graph theory, signal processing, number theory and data structures, and extracts the mechanisms common to them: recursive halving governed by the Master Theorem, tree-based representation of problem structure, and transform-domain reformulation.
The framework half is the more interesting claim. Rather than treating O(n log n) as an empirical ceiling that good algorithms happen to reach, it argues the bound is a consequence of information-theoretic limits on comparison-based and information-limited problems — making the log factor the price of the decisions the algorithm must make, not an artefact of the divide-and-conquer style.
The paper is also explicit about the boundary. It identifies classes of problems where the principle does not apply, which is what separates a framework from a slogan — a principle that explained everything would explain nothing.
Every number, and what stands behind it
A claim is only worth the evidence attached to it. Each row below carries its basis: measured on the author’s own hardware, derived from the construction, measured on synthetic data, projected from literature, or simply cited.
| Claim | Figure | Basis | Context |
|---|---|---|---|
| Fields surveyed | 7 | Derived | Sorting, arithmetic, geometry, graphs, signals, number theory, data structures |
| Target reduction | O(n²) → O(m log n) | Derived | The pattern the survey extracts |
| Lower bound argued | Ω(n log n) | Derived | For comparison-based and information-limited problems |
| Unifying mechanisms | divide-and-conquer, tree structure, information limits | Derived | The framework’s three-part claim |
| Formal apparatus | Master Theorem + information theory | Cited | Standard results, applied as the unifying lens |
Measured — author-run experiment on the stated setup. Synthetic — measured, but on synthetic rather than real data. Derived — follows from the stated construction or proof. Projected — paper-stated projection, not an author-run benchmark. Cited — taken from external literature.
How it works
- Master Theorem recurrences. The divide-and-conquer half: recursion depth log n, linear merge, n log n total.
- Tree-based structural representation. Problems reframed so their structure is a tree, at which point the depth is the log factor.
- Information-theoretic lower bounds. The decision-tree argument that makes n log n a floor rather than a target.
- Explicit non-applicability. Problem classes where the principle fails are named, which is what keeps it falsifiable.
What it does not do
Taken from the folder’s own README. Nothing here has been softened.
- This is a survey and a synthesis. Nothing in it is a new algorithm or a new bound.
- The unification is an argument from resemblance across cases, not a theorem that the mechanisms are the same mechanism.
- Some of the cases surveyed have reductions with genuinely different structure that the framing smooths over.
- The lower-bound results cited are standard; the paper’s contribution is organisational.
- No implementations, no measurements.
Free under AGPL-3.0+ for almost everyone
Personal use, charities, education and organisations under AUD 50,000 a year pay nothing. A tiered commercial licence covers everyone else.