Big-O basics

What you'll learn

What Big-O notation is, and how to tell constant, linear and quadratic work apart.

Why it matters

Two programs can give the same answer, but one finishes in a blink and the other takes hours on a big input. Big-O is the shared language for talking about that difference.

Explanation

Big-O describes how the amount of work grows as the input gets bigger. We call the input size n. We do not measure seconds, because a faster laptop would change them. We count steps.

The three you will meet first:

• O(1), constant: the same work no matter how big n is. Looking up one item by its position.
• O(n), linear: work grows in step with n. Checking every item once.
• O(n squared), quadratic: work grows with n times n. Comparing every item with every other item.

Big-O ignores small details. 3n + 5 is just O(n), because when n is huge, only the shape of growth matters.

Example

const items = [4, 8, 15, 16, 23, 42];

// O(1): one step, however long the list is
console.log(items[0]);

// O(n): visits each item once
let sum = 0;
for (const x of items) {
  sum += x;
}
console.log(sum);

// O(n squared): every item paired with every item
let pairs = 0;
for (const a of items) {
  for (const b of items) {
    pairs++;
  }
}
console.log(pairs);

Step-by-step walkthrough

1. items[0] jumps straight to the first item: 1 step. Printing 4.
2. The first loop visits all 6 items once: 6 steps. The sum is 108.
3. The nested loop runs the inner loop 6 times for each of the 6 outer items: 36 steps. It prints 36.
4. Double the list to 12 items and the single loop does 12 steps, but the nested loop does 144.

Try it yourself

Change the list to have 10 items and watch the pairs count. Is it 10 or 100?

Common mistakes

• Measuring seconds instead of growth. Big-O is about how work scales, not exact speed.
• Thinking O(n) is always "slow". For small inputs it is fine. It matters when n is large.
• Counting constants. O(2n) is just O(n).
• Assuming nested loops are always O(n squared). Only if both loops run to n.

Quick quiz

Summary

• Big-O describes how work grows with input size n.
• O(1) constant, O(n) linear, O(n squared) quadratic.
• Ignore constants and small terms.

Next: arrays, the most basic data structure.