Big O Notation

⏱ 6 min✏️ Quiz at the end

Introduction

Imagine two people describing the same road trip. One says "it took four hours, seventeen minutes, and six seconds." The other says "it's about four hours β€” give or take, depending on traffic." The second description is less precise, but it is far more useful for planning, because it captures the shape of the situation rather than one exact measurement taken under one specific set of conditions. Big O notation is computer science's version of that second, more useful description. It is a way of summarising how the running time (or memory use) of an algorithm grows as the size of its input, usually written n, gets larger β€” without getting distracted by the particular computer, programming language, or day of the week the code happened to run on.

Why Not Just Time It With a Stopwatch?

Timing a program in seconds tells you about one machine, one moment, one input. Swap in a faster laptop and the seconds shrink, but the algorithm hasn't changed. Comparing algorithms properly means asking a machine-independent question: as n doubles, does the work double too? Triple? Barely move? Big O answers that question with a compact label.

The Common Growth Rates

A handful of growth rates show up again and again, usually listed from best to worst:

  • O(1) β€” constant. The work doesn't depend on n at all. Looking up a value at a known position in an array is O(1): whether the array holds ten items or ten million, the lookup takes one step.
  • O(log n) β€” logarithmic. The work grows very slowly because each step eliminates a large chunk of the remaining possibilities. Binary search is the classic example: doubling the list size adds only one extra comparison.
  • O(n) β€” linear. The work grows in direct proportion to n. A linear search that checks every item once is O(n): double the list, double the checks.
  • O(n log n) β€” "linearithmic". Slightly worse than linear, and the signature of efficient sorting algorithms like merge sort β€” split the problem repeatedly (the log n part), then do linear work at each level.
  • O(nΒ²) β€” quadratic. The work grows with the square of n. This is the classic signature of a loop nested inside a loop over the same data, such as comparing every pair of items.
  • O(2^n) β€” exponential. The work doubles with every additional item. Algorithms with this growth rate become unusable almost immediately as n climbs past a few dozen.

Worst Case, Not Average Case

By convention, Big O most commonly describes the worst case β€” the most steps an algorithm could possibly need, for the least convenient possible input. This might sound pessimistic, but it is the safer number to plan around: a system that promises O(n) worst-case behaviour will never surprise you with a sudden slowdown on unlucky input.

Why Constants and Small Terms Get Dropped

An algorithm that does 3n + 7 steps is still written as O(n), not O(3n + 7). Big O cares about the shape of the growth curve as n becomes very large, not the exact step count for any one input size. Once n is large enough, the difference between n and 3n matters far less than the difference between n and nΒ² β€” so Big O strips away constants and lower-order terms to leave the dominant term that will eventually dwarf all the others.

Key Words

  • Big O notation β€” shorthand describing how an algorithm's resource use grows as input size grows
  • n β€” the conventional symbol for input size
  • Worst case β€” the input that makes an algorithm do the most possible work
  • Dominant term β€” the part of a step-count formula that matters most as n grows large

Questions & comments

Comments are public and are checked before they appear. Please don’t post your full name, email, phone number, school, or anything else that identifies you. How we use this.

Loading comments…

1000 characters left Β· links are not allowed