Big-O notation

When two programs both solve the same problem, which one should you trust to stay fast as the data grows? You cannot answer that by timing them once on a small input, because hardware, language, and luck all interfere. Big-O notation gives a hardware-independent way to compare algorithms by describing how their cost grows as the input gets larger.

What Big-O actually measures

Big-O expresses an upper bound on growth. We write the input size as n and ask: as n heads toward infinity, how does the work scale? An algorithm that is O(n) does work roughly proportional to the input size; one that is O(n^2) does work proportional to the square of the input size.

Crucially, Big-O throws away two things: constant factors and lower-order terms. An algorithm that takes 3n^2 + 5n + 100 steps is simply O(n^2). This looks careless, but it is the whole point. The constant 3 depends on your CPU and compiler; the + 100 is irrelevant once n is large. What survives is the term that dominates at scale, and that term predicts how the program behaves when it matters most.

The common complexity classes

A handful of growth classes cover most code you will meet, listed here from best to worst:

• O(1) — constant. Cost is independent of input size. Indexing into an array or reading a hash-table entry. Adding a million more items changes nothing.
• O(log n) — logarithmic. Cost grows by a fixed amount each time n doubles, because the problem is repeatedly halved. Binary search is the textbook case. Even for a billion items, only about thirty steps are needed.
• O(n) — linear. Cost grows in step with the input. Scanning a list to find the largest value. Double the input, double the work.
• O(n log n) — linearithmic. Slightly worse than linear. This is the bound for efficient comparison sorts like merge sort and heapsort, and no comparison-based sort can do better in the worst case.
• O(n^2) — quadratic. Typical of nested loops over the same data, such as comparing every pair of elements. Double the input and the work quadruples. This scales poorly and is a common target for optimization.

To feel the difference, imagine n = 1,000,000. A logarithmic algorithm finishes in about 20 steps, a linear one in a million, and a quadratic one in a trillion. The class, not the constant, decides whether your program finishes today or next year.

Worst, average, and best case

The same algorithm can have different costs depending on the input. Worst-case complexity is the maximum cost over all inputs of a given size, and it is what Big-O usually reports because it gives a guarantee. Average-case is the expected cost over typical inputs. A hash-table lookup is O(1) on average but O(n) in a pathological worst case where everything collides.

A rule of thumb: when someone says an algorithm “is O(n log n)” without qualification, they almost always mean the worst case.

Cousins of Big-O

Big-O has two siblings worth knowing. Big-Omega describes a lower bound — the best the algorithm can do. Big-Theta is a tight bound, used when the upper and lower bounds match, meaning the growth is pinned exactly. In everyday engineering conversation people say “Big-O” loosely even when they mean Theta, but the precise vocabulary matters in formal analysis.

Beyond time: space complexity

Big-O is not only about time. The same notation describes how memory usage grows with input size. An algorithm that builds a copy of its input uses O(n) extra space; one that sorts in place may use only O(1) extra space. Real engineering often trades one against the other — spending more memory to save time, or vice versa.

Why it is worth the abstraction

It is tempting to dismiss Big-O as academic. But the discipline of asking “how does this scale?” is exactly what separates code that works on a demo from code that survives production. A quadratic loop hidden inside a function is invisible at ten records and catastrophic at ten million. Big-O gives you the language to spot that danger before it ships — and to reason clearly about which algorithm to reach for in the first place.