One Symbol, Two Stories
By now you know that every numerical answer is an approximation, and that we measure how wrong it is with absolute error and relative error. This guide adds the single most useful piece of shorthand in the whole field: big-O notation. The catch — and the reason beginners get confused — is that the same letter O is used for two completely different things. One O describes how your error behaves as you work harder; the other describes how much work that is.
Think of writing "O(h^2)" or "O(n^3)" as a verbal shrug that throws away constants and keeps only the trend. We do not care whether the error is exactly 3.7 h^2 or 0.02 h^2; we care that halving h roughly quarters the error. We do not care whether a solve takes 2 n^3 or 0.5 n^3 operations; we care that doubling n makes it about eight times slower. Big-O keeps the slope and drops the clutter.
Formally, f(h) = O(h^p) as h goes to 0 means |f(h)| <= C h^p for some constant C and all small enough h. And g(n) = O(n^3) as n grows means g(n) <= C n^3 for large n. Same definition, opposite limits: accuracy watches h shrink toward 0, cost watches n grow toward infinity. Throughout this guide, keep that orientation in mind — it is the compass that tells you which story a given O is telling.
Big-O Story One: Order of Accuracy, O(h^p)
Many methods have a knob called the step size h — the spacing of a grid, the time step of a simulation, the gap used in a difference quotient. The order of accuracy p tells you the exponent in the error: error roughly equals C h^p. The bigger p is, the faster the error melts as you shrink h. A first-order method, O(h), halves its error when you halve h. A second-order method, O(h^2), quarters it. A fourth-order method, O(h^4), divides it by sixteen. That difference is enormous in practice.
Where does that h^p come from? Almost always from a Taylor expansion. Take the simplest derivative estimate, the finite-difference formula (f(x+h) - f(x))/h. Taylor says f(x+h) = f(x) + h f'(x) + (h^2/2) f''(x) + ..., so the quotient equals f'(x) + (h/2) f''(x) + ..., leaving an error of O(h): first order. The leftover terms you chopped off are exactly the truncation error. Switch to the central difference (f(x+h) - f(x-h))/(2h) and the odd terms cancel, lifting it to O(h^2). The cancellation buys you an extra power for free.
Big-O Story Two: Cost, O(n^3)
The second O measures the work an algorithm does as the problem size n grows — its computational complexity. For a dense linear system A x = b with n unknowns, solving by Gaussian elimination (which produces an LU factorization) costs about (2/3) n^3 arithmetic operations, so we say O(n^3). The honest unit here is the flop count — the number of floating-point adds and multiplies. Double n and the work grows roughly eightfold; that single fact decides whether a model finishes overnight or never.
n O(n) O(n log n) O(n^2) O(n^3) 100 1e2 ~7e2 1e4 1e6 1,000 1e3 ~1e4 1e6 1e9 10,000 1e4 ~1.3e5 1e8 1e12
This is where the genius of good numerical methods lives. Multiplying two n-by-n matrices is O(n^3); a naive discrete Fourier transform is O(n^2), but the fast Fourier transform reorganizes the same sums into O(N log N) and turns an hour into a blink. Or recall factor once, solve many: the LU factorization costs O(n^3), but each later solve with a new right-hand side b is only O(n^2). If you must solve A x = b for many b, you pay the cubic once and the quadratic many times — never re-eliminate from scratch.
Reading the Slope: A Numerical Experiment
You rarely have to trust a textbook's claim about p — you can measure it. Run a method twice, with step sizes h and h/2, and compare the errors. If error is C h^p, then halving h should divide the error by 2^p. So the observed ratio error(h)/error(h/2) reveals p: about 2 means first order, about 4 means second order, about 16 means fourth. This little check is the everyday tool of the trade.
- Pick a problem whose true answer you know, so you can compute a real error (e.g. estimate f'(x) where you know the exact derivative).
- Run the method at step size h and record the error e1; run it again at h/2 and record e2.
- Form the ratio e1/e2. Take p = log2(e1/e2): a ratio near 4 gives p near 2, confirming a second-order method.
- Repeat down a sequence of shrinking h and watch p settle. If p suddenly drops, you have hit the round-off floor — stop shrinking h.
This experiment connects directly to the next guide on order of convergence: an iterative method like Newton's method has its own order p (Newton is quadratically convergent, p = 2, near a simple root), but there p describes how the error from one step x_n to the next x_{n+1} shrinks, not how a grid spacing h affects a single answer. Same big-O idea, applied to a sequence instead of a step size.
The Only Question That Matters: Accuracy per Second
Now put the two O's in the same room, because real choices are trades between them. A higher-order method (big p) reaches a target accuracy with a much coarser grid — fewer points, fewer unknowns, lower cost. A faster method (small complexity) lets you afford a finer grid in the same time budget. The practitioner's question is never "which is more accurate" or "which is cheaper" alone, but the joint one: which method delivers the accuracy I need within the time and memory I have?
A concrete tension: a fourth-order method might cost more flops per grid point than a second-order one, yet win decisively because it needs vastly fewer points to hit the same error. But high order is not a free lunch — it usually demands extra smoothness from the problem, and it can be more fragile near kinks, shocks, or noisy data, where a sturdy low-order method quietly wins. Big-O tells you the asymptotic trend; it stays silent about the constant C and about small problems where that constant dominates.
And keep your two error sources straight. Big-O for accuracy controls only the discretization or truncation error — the price of approximating with a finite step. It says nothing about conditioning: a beautifully high-order, perfectly cheap algorithm still produces garbage if the underlying problem is ill-conditioned, because accuracy = conditioning x stability, not algorithm cleverness alone. Big-O budgets your effort; it does not repair an ill-posed question.