Computational Complexity, Feasibility Estimation, and Proving Algorithms Correct
The two questions to ask before writing any code: will it finish, and will it be right? Plus the disciplined optimization of brute force.
Leads to: This is the habit you carry into every Euler Lab problem - and into every production research job.
Learning Objectives
Click a status chip to cycle: Not started → In progress → Studied → Practiced → Needs review → Mastered.
- Define \(O,\ \Omega,\ \Theta\) precisely and use them without the common abuses.
- Estimate whether an algorithm will finish, using an operations budget and a realistic constant for the language.
- Prove an algorithm correct with a loop invariant and a termination (variant) argument.
- Optimize a brute force systematically: prune, restructure, precompute, reformulate - in that order.
- Compare growth rates numerically and identify the crossover point where the asymptotically better algorithm actually wins.
Key Vocabulary
- Big-O
- \(f=O(g)\) iff \(\exists C,n_0:\ f(n)\le Cg(n)\ \forall n\ge n_0\). An upper bound - it says nothing about tightness.
- Big-Theta
- \(f=\Theta(g)\) iff \(f=O(g)\) AND \(f=\Omega(g)\). This is what you usually mean when you say ‘the complexity is’.
- Operations budget
- A rough count of primitive operations you can afford: \(\sim10^8\) simple ops/second in C, \(\sim10^6\!-\!10^7\) in pure Python.
- Loop invariant
- A property true before the loop, preserved by each iteration, and strong enough at exit to give the result. The standard correctness proof.
- Variant / measure
- A non-negative integer that strictly decreases each iteration - the termination half of the proof (well-ordering, as in Euclid).
- Pseudo-polynomial
- Polynomial in the numeric VALUE of an input but exponential in its bit length (e.g. the \(O(nW)\) knapsack DP).
- Crossover point
- The \(n\) beyond which an asymptotically better algorithm actually beats a worse one with a smaller constant. It is often much larger than you expect.
Intuition & Motivation
Asymptotics, precisely
Constants and lower-order terms are dropped because they do not affect the growth rate - but they absolutely affect whether your program finishes today. Asymptotics rank algorithms; a budget decides feasibility. You need both, and confusing them is the classic beginner error in both directions.
The feasibility estimate
| \(n\) | \(O(n^2)\) | \(O(n^3)\) | \(O(2^n)\) | \(O(n!)\) |
|---|---|---|---|---|
| 10 | 100 | 1 000 | 1 024 | 3.6M |
| 20 | 400 | 8 000 | 1M | 2.4×10^18 - hopeless |
| 100 | 10 000 | 1M | 10^30 - hopeless | - |
| 1 000 | 1M | 10^9 - borderline | - | - |
| 10^6 | 10^12 - hopeless | - | - | - |
Read this table as a set of hard walls. In pure Python, \(10^6\) loop iterations is a comfortable second; \(10^8\) is a coffee break; \(10^{10}\) is never. So a \(\Theta(n^2)\) algorithm at \(n=10^5\) (\(10^{10}\) ops) is not ‘slow’ - it is infeasible, and the fix must change the exponent, not the code.
Interactive: where does the crossover actually happen?
Proving it right: invariant + variant
An algorithm is correct when you can state (i) a loop invariant - a property that holds before the loop, is preserved by every iteration, and at termination implies the goal - and (ii) a variant - a non-negative integer that strictly decreases, guaranteeing termination by well-ordering.
Optimizing a brute force, in order
‘Brute force is too slow’ is a diagnosis, not a plan. Apply these four moves in order, and stop as soon as you are under budget:
- Prune. Reject partial candidates early (19.10). Costs nothing, often buys orders of magnitude, never changes the exponent.
- Restructure the loops. Hoist invariant work out of the inner loop; iterate over the smaller set; break as soon as the answer is decided. Constant-factor wins - but a \(100\times\) constant is the difference between a coffee break and a second.
- Precompute / cache. Sieve once and query many (19.2); memoize the recursion (19.7); build a factorial table (19.5). This is usually where an \(O(n\sqrt n)\) becomes an \(O(n\log\log n)\).
- Reformulate. Change the algorithm class: closed form, matrix power (19.13), meet-in-the-middle (19.10), generating function (19.6), a mathematical identity that collapses the sum. This is the only move that changes the EXPONENT - and it is the move that most problems are secretly testing.
The ordering is deliberate: the first three are cheap and safe, and they buy you the time to think about the fourth. But if the feasibility estimate says you are \(10^6\times\) over budget, skip straight to (4) - no amount of pruning closes a gap of six orders of magnitude.
Coding workbench
Every problem in the Euler Lab is, at bottom, a feasibility puzzle: the naive reading of the statement is always computable in principle and always too slow in practice. The stated bound (‘below two million’, ‘the \(10\,001\)st prime’, ‘term \(10^{15}\)’) is a message about the intended complexity class. Learning to read that message is the single most transferable skill in this phase - and it is exactly the skill a quant research job tests when it asks whether your backtest will finish before the meeting.
- Saying ‘it’s \(O(n^2)\), that’s fine’ without knowing \(n\). Complexity without a number is not an estimate.
- Optimizing the constant when the exponent is wrong. A \(100\times\) speedup of an \(O(2^n)\) algorithm buys you \(\log_2 100\approx6.6\) more elements. That is all.
- Confusing \(O\) with \(\Theta\), then concluding an algorithm is slow because someone quoted a loose upper bound.
- Ignoring memory. \(O(n^2)\) time is often fine at \(n=10^5\); \(O(n^2)\) MEMORY at \(n=10^5\) is 80 GB and will not run at all.
- Trusting a benchmark on small inputs. Constants dominate below the crossover, so the asymptotically-worse algorithm often looks faster in your test - and then dies in production.
- Skipping the correctness proof because the code ‘passes the examples’. An invariant that you can state in one sentence catches bugs that no test suite will.
- Estimate on paper first. Count states, count work per state, multiply, compare to \(10^7\) (Python) or \(10^8\) (C). Ten minutes of arithmetic beats an hour of waiting.
- The input bound in the problem statement is a hint about the intended algorithm. \(n\le20\) screams bitmask; \(n\le10^{18}\) screams \(O(\log n)\) or a formula.
- When you must speed up pure Python by a constant: vectorize with NumPy (Phase 17), use bytearray/big-int bitsets (19.8), and hoist everything you can out of the inner loop. Expect \(10\text{–}100\times\), never \(10^6\times\).
- Always keep the brute force. It is your oracle: run it on small inputs and diff against the fast version. Every optimization in this phase should be validated that way (this is Pragmatic Programmer’s point about testing against a reference implementation).
- State the invariant in a comment above the loop. If you cannot state it, you do not yet understand your own algorithm - and that is the moment to stop typing.
Practice this in the Euler Lab
Computational problems that exercise exactly this technique. Each opens in the Euler Lab with a Python workbench, a progressive hint ladder, and answer checking. Tier A/B run at full scale in the browser.
Warm-up:
#39 Integer Right Triangles (2%, tier A) #11 Largest Product in a Grid (5%, tier A) #44 Pentagon Numbers (6%, tier A) #18 Maximum Path Sum I (7%, tier A)
Applied:
#485 Maximum Number of Divisors (19%, tier B) #190 Maximising a Weighted Product (21%, tier B) #183 Maximum Product of Parts (23%, tier B)
Challenge:
#147 Rectangles in Cross-hatched Grids (41%, tier C) #161 Triominoes (41%, tier C)
745 Project Euler problems in total are mapped to this lesson. Open the Euler Lab to filter them all.
Knowledge Check
Practical Exercise
(a) You must count pairs \((i,j)\) with a property, over \(n=2\times10^5\) items. The obvious algorithm is \(O(n^2)\). Estimate its cost, decide feasibility, and name two reformulations that could change the exponent. (b) Give a loop invariant and a variant for the Euclidean algorithm (19.1) and conclude both correctness and the \(O(\log\min(a,b))\) bound. (c) An \(O(n\log n)\) algorithm has constant 200; an \(O(n^2)\) one has constant 1. Find the crossover \(n\) and say which you would ship.
(a) \(n^2=4\times10^{10}\) operations. At \(10^7\) ops/s (Python) that is \(4\times10^3\) seconds ≈ 67 minutes at the very best, realistically many hours - infeasible for an interactive workflow, and no amount of tuning fixes a factor of \(10^4\). Reformulations that change the exponent: (i) sort and sweep - if the property is order-related (e.g. \(a_i+a_j\le K\)), sort once and use two pointers or binary search: \(O(n\log n)\); (ii) hash/count complement - if the property is an equality (e.g. \(a_i+a_j=K\)), pass once with a hash map of complements: \(O(n)\). Both replace ‘examine every pair’ with ‘examine every element, and look up what it needs’ - the standard \(n^2\to n\log n\) move.
(b) Invariant: \(\gcd(a,b)\) is unchanged by the update \((a,b)\mapsto(b,\ a\bmod b)\) - proved in 19.1 by showing the two pairs have identical common-divisor sets. Variant: the second argument \(b\), a non-negative integer, strictly decreases (since \(a\bmod b\lt b\)). By well-ordering the loop terminates, and at termination \(b=0\), where the invariant gives \(\gcd(a,0)=a\) - the returned value is the gcd. Bound: the variant more than halves every two steps (\(a\bmod b\lt a/2\) in either case), so the number of iterations is \(O(\log\min(a,b))\). The same two objects gave correctness, termination AND complexity.
(c) Solve \(200\,n\log_2 n = n^2\), i.e. \(n=200\log_2 n\). Try \(n=2000\): \(200\log_2 2000\approx200\times11=2200\gt 2000\). Try \(n=2400\): \(200\times11.2=2240\lt 2400\). So the crossover is near \(n\approx2200\). Which to ship? If \(n\) is always below ~2000, the quadratic is genuinely faster AND simpler - ship it, and say so in a comment. If \(n\) can grow, ship the \(O(n\log n)\): at \(n=10^6\) it is \(4\times10^9\) vs \(10^{12}\), a 250× win that keeps growing. The right answer depends on the input distribution, which is why ‘what is \(n\)?’ is always the first question.
Lesson Summary
Retrieval Practice
Close the lesson and answer from memory before checking. This is deliberate, effortful recall - the single highest-yield study action.
A: Feasibility: |states| × work-per-state versus an ops budget (\(\sim10^7\)/s in Python, \(10^8\)–\(10^9\) in C/NumPy). Correctness: a loop invariant (preserved each iteration, implies the goal at exit) plus a non-negative variant that strictly decreases (termination).
A: A \(c\)-fold speedup shifts the feasible input size by only \(\log_2 c\), since \(2^{n+\Delta}=2^n2^\Delta\). A 1000× optimization buys about 10 extra elements. Only changing the algorithm class (the exponent) helps.
Completion Checklist
- I can explain the core ideas in my own words
- I worked the derivations/examples by hand
- I completed the interactive workbench(es)
- I passed the knowledge check
Source References
This lesson synthesizes and paraphrases concepts from the sources below. No copyrighted text, problem sets, or solutions are reproduced. Return to the originals for full depth.
- Numerical Linear Algebra (Trefethen & Bau, SIAM, 1997) foundational - Lectures 12–15, 32 - Operation counts, flop budgets, conditioning and stability - the numerical-analysis tradition of estimating cost and error BEFORE running anything.
- The Pragmatic Programmer (Thomas & Hunt, 2nd/20th Anniv. ed., 2019) current - Ch. 2 (Estimating) & Ch. 7 - Estimation, the ‘good-enough’ principle, and testing a fast implementation against a slow reference oracle - the engineering half of this lesson.
- Calculus, Vol. I (Tom Apostol, 2nd ed., 1967) foundational - Ch. I.4 - Induction and well-ordering: the formal machinery behind loop invariants and variant-based termination proofs.
- A Mind for Numbers (Barbara Oakley, 2014) foundational - Ch. 4–5 - Chunking and deliberate practice: the feasibility triage becomes automatic only after you have done it by hand on a dozen problems.