In complexity theory, "computability alone isn't enough — efficiency matters." What independent properties does complexity measure?
The growth rate of resources (time, memory, network) the algorithm needs as input size grows — independent of the particular CPU, language, compiler, or test data.
The point is to compare algorithms abstractly. We don't care how fast a 2024 laptop runs your code; we care how the runtime scales when the input doubles in size.
The Landau / Big-O classes:
| Class | Growth | Example | Tractable? |
|---|---|---|---|
| O(1) | Constant | Array lookup | Yes |
| O(log n) | Logarithmic | Binary search | Yes |
| O(n) | Linear | Linear scan | Yes |
| O(n log n) | Linearithmic | Mergesort | Yes |
| O(n²) | Quadratic | Bubble sort | Yes (for small n) |
| O(2ⁿ) / O(eⁿ) | Exponential | Brute-force key search | No — explodes |
Why this matters for crypto: the defender needs encryption/decryption to be polynomial (fast — O(n²) or so for big-int multiplication). The attacker, to break the scheme, needs to solve a problem that is exponential in the key size. Doubling the key doubles the defender's work but squares the attacker's, so the gap widens exponentially.
Tip: If a "fast attack" emerges (like a polynomial algorithm for factoring), the entire defender/attacker asymmetry collapses. That's exactly why post-quantum crypto is being standardised — Shor's algorithm makes factoring polynomial on a quantum computer.