Big O

Intuition

Imagine looking up a word. Reading a dictionary page by page takes longer the bigger the dictionary: double the pages, double the work. Opening it in the middle and halving the search each time barely notices the size: double the pages, one more step.

Big O names that difference. It doesn’t count seconds. It describes the shape of the growth, so you can tell which approach will still work when the input is a thousand or a million times bigger.

How to read it

Count the steps an algorithm takes for an input of size n, then keep only the part that dominates as n grows:

1. Drop constants. 3n steps and n steps are both O(n). Constants depend on the machine and language; the shape doesn’t.
2. Keep the biggest term. n² + 5n + 20 is O(n²). At n = 1,000, the n² part is 1,000,000 and the rest is about 5,000.
3. Nested loops multiply. A loop over n inside another loop over n is O(n²). Two loops one after the other are O(n) + O(n), which is still O(n).
4. Halving gives a log. If each step throws away half of what’s left, the step count is about log₂ n.

The common classes

In code

The three functions below do very different amounts of work on the same list. Count the loops:

def first(items):  # O(1)
    return items[0]


def contains(items, target):  # O(n)
    for item in items:
        if item == target:
            return True
    return False


def has_duplicate(items):  # O(n²)
    for i in range(len(items)):
        for j in range(i + 1, len(items)):
            if items[i] == items[j]:
                return True
    return False

function first(items) { // O(1)
  return items[0];
}

function contains(items, target) { // O(n)
  for (const item of items) {
    if (item === target) return true;
  }
  return false;
}

function hasDuplicate(items) { // O(n²)
  for (let i = 0; i < items.length; i++) {
    for (let j = i + 1; j < items.length; j++) {
      if (items[i] === items[j]) return true;
    }
  }
  return false;
}

func first(items []int) int { // O(1)
	return items[0]
}

func contains(items []int, target int) bool { // O(n)
	for _, item := range items {
		if item == target {
			return true
		}
	}
	return false
}

func hasDuplicate(items []int) bool { // O(n²)
	for i := 0; i < len(items); i++ {
		for j := i + 1; j < len(items); j++ {
			if items[i] == items[j] {
				return true
			}
		}
	}
	return false
}

fn first(items: &[i32]) -> i32 { // O(1)
    items[0]
}

fn contains(items: &[i32], target: i32) -> bool { // O(n)
    for &item in items {
        if item == target {
            return true;
        }
    }
    false
}

fn has_duplicate(items: &[i32]) -> bool { // O(n²)
    for i in 0..items.len() {
        for j in i + 1..items.len() {
            if items[i] == items[j] {
                return true;
            }
        }
    }
    false
}

first touches one item no matter how long the list is. contains may check every item once. has_duplicate compares every pair, about n²/2 comparisons.

Common mistakes

1. Treating Big O as speed. It predicts how the cost scales, not how fast one run is.
2. Forgetting the hidden loop. x in list, indexOf and list.remove are O(n) each. Inside another loop they make the whole thing O(n²).
3. Adding when you should multiply. Loops one after the other add; loops inside loops multiply.
4. Ignoring space. Making a copy of the input is O(n) extra memory, even when the time is fine.

Check yourself

Sources

• Cormen, Leiserson, Rivest and Stein, Introduction to Algorithms, chapter 3, “Characterizing Running Times.”
• Donald Knuth, “Big Omicron and Big Omega and Big Theta,” ACM SIGACT News 8, no. 2 (1976): 18–24.