Big-O Notation & Algorithm Efficiency

Two programs solve the same problem. One is fine on a million records; the other grinds to a halt on a thousand. Big-O notationis the language that captures that difference — not how fast an algorithm is, but how well it scales.

What Big-O measures

Big-O describes how the amount of work an algorithm does grows as the size of its input, n, grows. It deliberately throws away detail that does not matter for large inputs: constant factors (is each step twice as fast?) and lower-order terms. What is left is the shape of the growth — the thing that decides whether an algorithm survives a big dataset.

So Big-O is not measured in seconds. It answers a sharper question: if I double the input, roughly how much more work is there? An O(n) algorithm does twice as much; an O(n²) algorithm does four times as much.

Big-O is about the slope of the growth, not the height of the curve at any one point.

See it: compare growth rates

The differences between complexity classes are invisible for tiny inputs and overwhelming for large ones. The graph below plots operations against input size n for each class at once, so you can watch the curves fan apart.

Select a class to draw it boldly, and drag the point to read the operations at a chosen n.

The common complexity classes

A handful of classes cover almost everything you will meet, listed here from best to worst:

• O(1) — constant. The work is fixed, whatever the input size. Reading array element a[i] by its index takes the same time in a list of ten or ten million.
• O(log n) — logarithmic. Each step throws away half the remaining data. A binary search of a sorted list finds any item in a handful of steps.
• O(n) — linear. The work is proportional to the input. A linear search that checks every item once is the classic example.
• O(n log n) — linearithmic. A little steeper than linear. Merge sort and the other efficient sorts live here.
• O(n²) — quadratic. Work grows with the square of n. Two nested loops over the same data, or bubble sort, give this.
• O(2ⁿ) — exponential. Work doubles with each extra input. Some brute-force approaches (trying every subset of n items) blow up like this and become unusable even for modest n.

Working out an algorithm’s Big-O

You rarely need to count operations exactly. Three rules get you the class quickly.

Nested loops multiply. A loop over n inside another loop over n runs n × n times — O(n²). Consecutive stages add: a loop over n followed by a separate loop over n is O(n) + O(n), which is still O(n). Finally, Big-O usually describes the worst case— the most work the algorithm could be forced to do — because that is the guarantee that matters.

Common mistakes

Practice

Where next?

Big-O comes to life when you watch it happen: the sorting algorithms guide runs O(n²) and O(n log n) methods side by side with live operation counts, so you can see these curves play out on a real list.