What Big O is actually measuring
Big O notation describes how an algorithm's resource use — usually running time, sometimes memory — grows as the size of its input grows, not how fast it runs on any particular machine or input. This distinction matters: two algorithms can have identical Big O complexity while one runs faster in practice on real hardware, because Big O deliberately ignores implementation details like processor speed, and instead isolates the underlying growth pattern as input size scales up. It's a tool for comparing how algorithms scale, not a stopwatch measurement of actual runtime.
Why constants and lower-order terms get dropped
An algorithm might have a precise runtime formula like 3n² + 5n + 2 operations for an input of size n. Big O notation would describe this as O(n²), dropping the constant 3, the lower-order term 5n, and the constant 2 entirely. This isn't sloppiness — it reflects what actually matters as n grows large. As n increases, the n² term eventually dominates the total regardless of the constants attached to it; for large enough n, the difference between 3n² and n² becomes comparatively insignificant next to the difference between any function that grows as n² and one that grows as n or n³. Big O captures the growth category an algorithm belongs to, which is the more durable, comparison-relevant fact once inputs get large.
The common complexity classes, from best to worst
O(1) — constant time. The operation takes the same amount of work regardless of input size. Accessing a specific element of an array by its index is O(1) — whether the array has 10 elements or 10 million, looking up array[5] takes the same single step.
O(log n) — logarithmic time. The work grows very slowly as input size grows, because each step eliminates a large fraction of the remaining possibilities. Binary search is the standard example — searching a sorted list of 1,000,000 items takes at most about 20 comparisons, because each comparison cuts the remaining search space in half.
O(n) — linear time. The work grows directly in proportion to input size. Scanning through every element of an unsorted list once, to find a specific value or compute a sum, is O(n) — doubling the list's size doubles the work required.
O(n log n) — linearithmic time. Common in efficient sorting algorithms (merge sort, quicksort in typical cases). Grows faster than linear but much slower than quadratic — an algorithm that has to make roughly log n passes, each doing n work.
O(n²) — quadratic time. Common in algorithms with nested loops over the same input, like a naive approach that compares every element to every other element. Doubling the input size roughly quadruples the work — this is where performance starts degrading noticeably as inputs grow.
O(2ⁿ) — exponential time. The work doubles with every additional unit of input size. Algorithms in this class (some brute-force approaches to combinatorial problems) become impractically slow very quickly — an input just slightly larger can push runtime from seconds to longer than is practical to wait for.
Worst case versus average case
Big O is often used to describe an algorithm's worst-case behavior — the maximum work required for any input of a given size — but it can also describe average-case or best-case behavior, and it's important to know which one is being cited. Quicksort, for example, has an average-case complexity of O(n log n) but a worst-case complexity of O(n²), which occurs on specific unlucky input orderings. Comparing two algorithms fairly requires comparing the same case (worst-to-worst, or average-to-average) rather than one algorithm's best case against another's worst case.
Why this matters beyond an academic exercise
Big O complexity has real practical consequences once data sizes grow large enough. An O(n²) algorithm and an O(n log n) algorithm might perform similarly on a list of 100 items, where the difference in operations is small enough not to matter. On a list of 10 million items, the same difference in complexity class can mean the difference between a program finishing in seconds versus one that doesn't practically finish at all — the growth-rate difference that felt academic at small scale becomes the dominant real-world factor once the input is large enough, which is precisely the situation Big O notation was built to help reason about ahead of time, before running the code on data at that scale.
Reading it as a tool, not a grade
Big O notation isn't a verdict on whether an algorithm is "good" or "bad" in isolation — an O(n²) algorithm can be entirely appropriate for small, bounded inputs, and choosing a more complex O(n log n) algorithm to replace it might not be worth the added implementation complexity if the input size never grows large enough for the difference to matter in practice. Its real value is as a comparison tool: given two candidate approaches to the same problem, and some sense of how large the input will realistically get, Big O provides a principled basis for predicting which one will actually perform better once that scale is reached.