computational complexity
Computational complexity is how the cost of an algorithm — usually the number of arithmetic operations (flops) or the time, sometimes the memory — grows as the problem gets bigger. It is the other meaning of big-O notation: work = O(f(n)) says the operation count is bounded by a constant times f(n) for large n, where n measures the problem size (the number of unknowns, data points, or grid cells). It is the budget side of the accuracy-cost-stability triangle.
What matters is the growth rate, because it decides whether a method scales. Summing n numbers is O(n) — linear, cheap. The fast Fourier transform is O(n log n) — nearly linear, which is why it is revolutionary. Multiplying two n-by-n matrices or solving a dense linear system by Gaussian elimination is O(n^3) — cubic, so doubling n multiplies the work by eight. An O(2^n) method is exponential and hopeless beyond tiny n. For solving A x = b: a dense LU solve is O(n^3), but the same answer for a tridiagonal system costs only O(n), and a well-preconditioned iterative method can approach O(n) for sparse problems — same answer, wildly different cost.
Complexity matters because cost, not just accuracy, decides what is possible: an O(n^3) algorithm that is fine for n = 1000 becomes a billion times more expensive at n = 1,000,000. But the big-O for cost shares the same caveats as the big-O for error: it is asymptotic, hides the constant (an O(n log n) method can lose to an O(n^2) one for small n), and counts operations, not wall-clock time. On modern hardware a low-flop method can run slowly if it moves a lot of memory — many real kernels are memory-bound, limited by cache misses and data movement rather than flop count, so complexity is necessary but not the whole story.
Solving the same A x = b: dense Gaussian elimination costs about (2/3) n^3 flops — O(n^3) — but if A is tridiagonal the Thomas algorithm gives the identical answer in about 8n flops — O(n) — millions of times cheaper at n = 1,000,000.
The growth rate, not the answer, decides feasibility at scale.
Big-O complexity counts operations, not real time. The hidden constant matters for small n, and on real hardware a memory-bound kernel is limited by cache misses and data movement, not flop count — low complexity does not guarantee speed.