Two functions can both "work" on a 100-row test table and behave completely differently at 10 million rows — one finishes in milliseconds, the other doesn't finish in a way anyone would wait for. Complexity analysis is how you know which one you're looking at before it's in production and it's too late to ask.
Why complexity matters
Wall-clock time depends on the machine, the language, the current load on the box — none of which tells you anything that transfers to a different machine or a bigger input. Complexity analysis throws all of that away on purpose and asks a narrower question: as the input size n grows, how does the amount of work grow with it? That question has the same answer on a laptop and a server, today and in five years, which is exactly why it's the thing worth reasoning about at design time — before a data structure or algorithm choice is load-bearing across a codebase and expensive to walk back.
Time complexity
Time complexity counts operations as a function of n, not seconds. A loop that touches every element of an n-element array once does n units of work regardless of whether each unit takes a nanosecond or a microsecond — the hardware-dependent constant is deliberately factored out, because it's not the thing that determines whether the algorithm is still usable at 100x the input size.
Space complexity
Space complexity is the same question asked about memory instead of operations: how much additional memory does the algorithm need as n grows? "Additional" is doing real work in that sentence — auxiliary space counts only the extra memory an algorithm uses beyond its input, while total space counts the input too. An in-place sort is typically described as O(1) auxiliary space (a constant amount of extra bookkeeping) even though the array it's sorting is sitting right there taking up O(n) — those are two different, both-correct numbers answering two different questions, and mixing them up is a common source of "wait, I thought this was O(1) space" confusion.
Best, worst, and average case
The same algorithm can do a different amount of work depending on which input of size n it gets, not just how big n is. Linear search for a target value in an unsorted array is the clearest example:
- Best case — the target is the first element. One comparison, regardless of how large the array is.
- Worst case — the target is the last element, or absent entirely. Every element gets compared.
- Average case — averaged over all possible target positions (assuming it's present and every position is equally likely), roughly half the array gets scanned.
Worst case is the one that matters most in practice for anything user-facing — it's the guarantee an adversarial or simply unlucky input can't exceed, which is exactly the property you need for a latency budget or an SLA. Average case matters more for capacity planning and throughput, where what happens typically, across many requests, is the relevant number.
Big O: the upper bound
Formally, f(n) = O(g(n)) means f doesn't grow faster than g — there exist positive constants c and n₀ such that f(n) ≤ c · g(n) for every n ≥ n₀. It's a ceiling: it says "this algorithm never does more than roughly g(n) work," and — this is the detail almost every informal explanation glosses over — a true upper bound is still technically correct even if it isn't tight. An algorithm that's actually O(n) is also, technically, O(n²) and O(2ⁿ) — those are all valid ceilings, just increasingly useless ones. When people say "this is O(n)" and mean the tightest, most informative description of its growth, what they're reaching for is actually the next notation.
Big Omega: the lower bound
f(n) = Ω(g(n)) is the mirror image: there exist constants c and n₀ such that f(n) ≥ c · g(n) for every n ≥ n₀. It's a floor — "this algorithm never does less than roughly g(n) work." Any comparison-based sorting algorithm is Ω(n log n) in the worst case, for instance — not because any particular algorithm happens to be that slow, but because there's a proven floor no comparison-based approach can beat, no matter how cleverly it's written.
Big Theta: the tight bound
f(n) = Θ(g(n)) means both hold at once — f is sandwiched between c₁ · g(n) and c₂ · g(n) for large enough n. This is the actual, tight description of an algorithm's growth, and it's what "Big O" almost always means in casual conversation even though that's not, strictly, what Big O notation says. Binary search is Θ(log n): it's both O(log n) (never worse) and Ω(log n) (never meaningfully better) — the bound is tight in both directions, not just an upper limit.
Two independent questions, not one
The single most common mix-up in this entire topic is treating "which case" (best/worst/average) and "which notation" (O/Θ/Ω) as the same axis — often stated as "Big O is worst case, Big Omega is best case." They're not the same axis. Case describes which input you're analyzing; notation describes how tightly you've characterized that specific case's growth. You can legitimately combine them any way the math supports:
| Case | Linear search | What it means |
|---|---|---|
| Best case | Θ(1) | Target is first — tightly constant, not just bounded above by a constant. |
| Worst case | Θ(n) | Target is last or missing — tightly linear. |
| Worst case | O(n²) | Also technically true — just a loose, uninformative ceiling nobody would actually quote. |
"The worst case is Θ(n)" and "the worst case is O(n)" are both correct statements about the same fact; Θ is just more informative because it also rules out the algorithm secretly being faster than linear in the worst case.
How fast the common classes actually diverge
Growth rate differences are easy to state and hard to feel until they're next to real numbers. Rounded operation counts for a few common classes:
| Class | n = 10 | n = 1,000 | n = 1,000,000 |
|---|---|---|---|
| O(1) | 1 | 1 | 1 |
| O(log n) | ~3 | ~10 | ~20 |
| O(n) | 10 | 1,000 | 1,000,000 |
| O(n log n) | ~33 | ~9,966 | ~19,931,569 |
| O(n²) | 100 | 1,000,000 | 1,000,000,000,000 |
| O(2ⁿ) | 1,024 | astronomically large | astronomically large |
At n = 10, every class in this table is usable. By a million, O(n²) has already crossed a trillion operations while O(n log n) is still under 20 million — the gap between "fine" and "not fine" opens up fast, and it opens up at exactly the input sizes that don't show up in a quick local test.
Practical tradeoffs
Asymptotic notation describes what happens as n grows without bound — it deliberately says nothing about the constant factor c hiding inside every one of these definitions, and at realistic, small-to-medium input sizes that constant can matter more than the growth class itself. This isn't a theoretical caveat; it's why two of the most widely used sorting implementations in production software are hybrids, not the theoretically cleaner algorithm alone:
- Python's Timsort falls back to a binary insertion sort for runs under 64 elements. Its own implementation notes justify this bluntly: below that size "it's hard to beat that given the overheads of trying something fancier" — insertion sort is Θ(n²) in the worst case, but its constant factor is small enough to win at small
n, where the setup overhead of a fancier O(n log n) approach dominates. - C++'s
std::sort(in libstdc++, via introsort) switches to insertion sort for partitions smaller than 16 elements, for the identical reason.
Both are deliberate engineering decisions made by people who understood the asymptotics perfectly well and chose the "worse" algorithm anyway, for the sizes where it actually wins. The same theme shows up as time-space tradeoffs elsewhere: a hash map spends O(n) extra space to turn an O(n) linear scan into O(1) average-case lookup; memoization spends space to turn exponential recomputation into linear time; an in-place sort keeps space at O(1) by accepting a more complex, sometimes slower algorithm than one that's free to allocate a second array. None of these is universally "correct" — picking between them means knowing both numbers for your actual input sizes, not just the asymptotic class of one of them in isolation.
Try it yourself
Big O Calculator turns the table above into something you can plug your own numbers into — enter an input size and see the exact operation count for all five classes at once, as a log-scale chart and a precise table side by side. Complexity Visualizer shows the same classes — plus O(2ⁿ) — as continuous growth curves on a chart you can drag through, including exactly where O(2ⁿ) permanently overtakes O(n²). Both run entirely in your browser.