Big-O Notation

You have a guest list and you want to know if anyone signed up twice. You write two versions of the check. With 100 names, both finish before you can blink. With a million names, one still finishes in a few milliseconds. The other takes several minutes.

Nothing about your laptop changed. The difference is how the amount of work grows when the list grows. Big-O notation is the tool for seeing that difference in the code, before you run it.

#Count steps, not seconds

Timing code with a stopwatch tells you about one machine, one input and one moment. Instead, count the basic steps the code does: comparisons, additions, lookups. Then ask how that count changes as the input size, called n, gets bigger.

Here is the slow duplicate check. It compares every name with every name after it. Step through it and watch the comparison counter.

for i from 0 to n - 1:  for j from i + 1 to n - 1:    if names[i] == names[j]:      return truereturn false

The exact count, n(n − 1) / 2, is more detail than you need. What matters is the shape: double the names and the work roughly quadruples. That shape is what Big-O captures.

#Keep only what grows fastest

To turn a step count into Big-O, do two things. Drop constant factors, and drop every term except the fastest-growing one.

Why is that allowed? Plug in a big number. With n = 1,000,000, the formula n²/2 − n/2 gives 500,000,000,000 minus 500,000. The second term changes the answer by about one part in a million. And the "divide by 2" does not change how the cost grows: double n and the work still quadruples. So n(n − 1) / 2 becomes O(n²), read "order n squared".

• 3n + 5 becomes O(n).
• n² + 100n becomes O(n²).
• 7 becomes O(1): the work does not depend on n at all.

#The growth rates you will meet

A handful of shapes cover almost every algorithm in this course. The picture shows how far apart they get.

A computer does very roughly a few hundred million simple steps per second. Read the last row again with that in mind: a million names with an O(n²) algorithm means minutes of work, while O(n) is done in milliseconds.

#Reading Big-O from code

You rarely need to write out a formula. Three rules get you most of the way:

1. Steps in a row add up, and the biggest wins. A loop over n, then another loop over n, is 2n, which is O(n).
2. Nested loops multiply. A loop over n inside a loop over n is O(n²).
3. Halving each time is O(log n). If every step throws away half of what is left, you can only do that about log₂(n) times. For a million items, that is 20 steps.

Now compare the two duplicate checks side by side. The second one remembers every name it has seen in a set, so checking "have I seen this before?" is one step instead of a whole loop.

// O(n²) time: compare every pair
function hasDuplicateSlow(names) {
  for (let i = 0; i < names.length; i++) {
    for (let j = i + 1; j < names.length; j++) {
      if (names[i] === names[j]) return true;
    }
  }
  return false;
}
 
// O(n) time: remember what you have seen
function hasDuplicate(names) {
  const seen = new Set();
  for (const name of names) {
    if (seen.has(name)) return true; // O(1) on average
    seen.add(name);
  }
  return false;
}

# O(n²) time: compare every pair
def has_duplicate_slow(names):
    for i in range(len(names)):
        for j in range(i + 1, len(names)):
            if names[i] == names[j]:
                return True
    return False
 
# O(n) time: remember what you have seen
def has_duplicate(names):
    seen = set()
    for name in names:
        if name in seen:  # O(1) on average
            return True
        seen.add(name)
    return False

#Memory counts too

Big-O works for memory the same way. The fast version stores up to n names in its set, so it uses O(n) extra space. The slow version only keeps two counters: O(1) space.

This is the most common trade in algorithms: spend memory to save time. Usually it is worth it. Sometimes, on a tiny device or a huge dataset, it is not. Knowing both numbers lets you choose on purpose.

#Worst case, unless someone says otherwise

If the duplicate happens to be the first two names, even the slow version stops after one comparison. Big-O usually describes the worst case, because that is the one that brings your app down. When people mean the average case, they say so, as with hash set lookups, which are O(1) on average.

#Check yourself

#What to practise next

The faster duplicate check worked because a hash set answers "have I seen this?" in one step. That idea is the whole of Hash Tables. To use it right away, solve Matching Receipts: the obvious solution is O(n²), and a map gets it to O(n).