The formula
The core statement is a bound, not an equation. For two functions of the input size n:
f(n) = O(g(n)) means there exist constants c > 0 and n0 > 0
such that |f(n)| <= c · g(n) for all n >= n0
Reading: past some threshold n0, f never climbs above a fixed multiple of g. That makes g an upper bound on the growth of f.
The companion bounds fill in the other two directions:
f(n) = Omega(g(n)) means f(n) >= c · g(n) for all n >= n0 (lower bound)
f(n) = Theta(g(n)) means both O and Omega hold (tight bound)
Reading: Omega says f grows at least as fast as g; Theta pins f to the same growth rate as g, top and bottom.
There is also the stronger "little-o," which uses a limit instead of a threshold:
f(n) = o(g(n)) means lim (n -> infinity) f(n)/g(n) = 0
Reading: f grows strictly slower than g — the ratio collapses to zero. Note 2n² = O(n²) is true, but 2n² = o(n²) is false, because the ratio settles at 2, not 0. Big-O tolerates a matching rate; little-o forbids it.
The reason engineers care: the constant c and the low-order terms disappear. 3n² + 500n + 9000 is O(n²). At n = 10, the 500n term dominates; by n = 100,000, the n² term buries everything else. Asymptotic analysis is the discipline of asking what wins when n is large, and only that.
Where you meet it
You meet it the first time a script that ran fine on a test file chokes on the real data set.
- The analysis script that scaled wrong. A vibration post-processor reads a run log and, for every sample, scans the whole list to find its nearest neighbor. That inner scan makes it
O(n²). On a 100-point bench check it returns instantly. On a 10-million-sample endurance run it becomes(10,000,000 / 100)² = 10,000,000,000×more work than the bench check — it never finishes. Sorting first, then walking the sorted list, drops it toO(n log n)and it completes in minutes. - Sizing a lookup on a test stand. You need to check each incoming telemetry frame against a table of known part IDs. A linear scan of the table is
O(n)per frame; a hash lookup isO(1)on average — worst caseO(n)under pathological collisions, so for a hard real-time deadline you quote the worst case or use a perfect hash / fixed-size table. At 50,000 frames per second, that difference is whether the DAQ keeps up or drops packets. - Design review, defending a choice. Someone asks why you picked a sort that's slower on the 12 rows in the demo. The answer is the growth curve: an
O(n log n)sort loses to insertion sort on tiny inputs but wins by orders of magnitude at production size. Big-O is the language that argument gets made in. - Memory budgeting on an embedded target. Space complexity is the same idea applied to RAM. An algorithm that materializes an
n × ndistance matrix isO(n²)in memory. On a box with 512 MB, that capsnnear 8,000 doubles per side before you're out of heap — the analysis tells you that before you deploy, not after the OOM kill.
How it works
The whole trick is that Big-O throws away everything except the fastest-growing term and its shape. That is a feature at scale and a trap at small scale.
Here is what the common orders actually do as n grows, verified numerically:
n O(log2 n) O(n) O(n log2 n) O(n^2)
100 6.6 100 664 10,000
10,000 13.3 10,000 132,877 100,000,000
1,000,000 19.9 1,000,000 19,931,569 1,000,000,000,000
10,000,000 23.3 10,000,000 232,534,967 100,000,000,000,000
Look at the log column: going from 100 records to 10 million — a 100,000× jump in data — the logarithmic cost only rises from about 7 to 23. That's why binary search feels like it doesn't care how big the array is. Now look at the n² column: the same jump multiplies the work by ten billion. Same input change, wildly different fate.
The classic mistake is trusting Big-O on small inputs. It is an asymptotic statement — it only promises anything past n0, and it says nothing about the constants. An O(n) algorithm with a huge constant can lose to an O(n²) one with a tiny constant until n gets large. Real libraries exploit this: many production sort routines run insertion sort (O(n²)) on subarrays under a few dozen elements, then switch to O(n log n) for the rest. The order of growth tells you the shape of the curve, not where two curves cross.
Second gotcha: Big-O is an upper bound, not a promise of tightness. Saying an algorithm is O(n²) is technically true even if it's really O(n) — n is bounded above by n². When you want the honest, both-sides answer, you want Theta. In casual engineering talk people say "big-O" and mean Theta; be aware the formal symbols disagree.
Third: know which case you're quoting. Quicksort is O(n log n) average but O(n²) worst case, when the pivots land badly on already-sorted data. If your test stand feeds it pre-sorted telemetry every time, the worst case is your normal case. Average-case Big-O assumes a distribution of inputs; a bench that always sends the same shape of data may sit exactly on the pathological input.
Last, the analysis ignores the machine. Cache misses, memory bandwidth, branch prediction, and disk seeks are all constant factors that Big-O erases — and on modern hardware a "constant factor" can be 100×. An O(n) pass that thrashes cache can lose to an O(n log n) pass that stays in L2. Big-O tells you which algorithm wins eventually; the profiler tells you which one wins today at your actual n. Use both.
History
The notation is older than computers by about eighty years, and it was born in number theory, not software.
The German number theorist Paul Bachmann introduced the O symbol in 1894, in the second volume of his Analytische Zahlentheorie, using it to describe the size of error terms in approximations. The letter stood for the German Ordnung — "order of" — which is why it's read as "order" and not the digit zero [1][2]. Bachmann was writing about how the remainder in a number-theory estimate behaved as a variable grew without bound; the idea of "how fast does the error grow" is exactly the idea software engineers later borrowed for "how fast does the runtime grow."
Edmund Landau, who worked the same analytic-number-theory territory, adopted Bachmann's O in his 1909 two-volume Handbuch der Lehre von der Verteilung der Primzahlen and popularized it so thoroughly that the whole family — big-O and the little-o he introduced alongside it — is still called "Landau notation" or "Landau symbols" today [1][3]. Hardy and Littlewood extended the toolkit in 1914 with an Omega symbol for lower bounds, though they defined it differently than modern computing does [1].
For most of a century the notation lived in pure and applied mathematics and had nothing to do with algorithms. That changed in the 1970s. Donald Knuth, deep in writing The Art of Computer Programming, brought the notation into algorithm analysis and, in a 1976 paper in ACM's SIGACT News titled "Big Omicron and big Omega and big Theta," cleaned up the definitions for computer science — arguing for the tighter Omega and Theta meanings that make the lower-bound and tight-bound claims useful when you're reasoning about running time [4]. That paper is the reason "O(n log n)" is now something you can say in a design review and have everyone in the room understand the same way.