Big-O: Counting Steps, Not Seconds

01Why it matters & the intuition

Every choice in this course — array or linked list, hash table or tree, BFS or DFS — is a trade-off measured in Big-O. Without it you cannot tell a clever solution from one that times out in production.

Think of it like…

Imagine finding a friend's name in a phone book. Reading every page is O(n). Opening the middle, then the middle of the half that must contain it, is O(log n). Knowing the exact page number is O(1). Big-O ignores how fast you flip pages; it only cares how the work grows as the book grows.

02See it move

Press play, then step through slowly. Change the input and predict the next frame before you click.

Growth race

interactive

Input size n = 16

O(1)

1 · 1 ms

O(log n)

4 · 4 ms

O(n)

16 · 16 ms

O(n log n)

64 · 64 ms

O(n²)

256 · 256 ms

O(2ⁿ)

65.5K · 4.3 s

Right column: rough time if each step were repeated a million times (and 2ⁿ at double the n) on a 1 GHz machine — the gap is what matters.

›At n = 16, O(n²) needs 256 steps while O(log n) needs 4. Bars use a log scale — each gridline is 10× more work.

03Key ideas

Drop constants

3n + 20 and n both grow linearly. Big-O describes the *shape* of growth, so it keeps only the dominant term: O(n).

Worst, average, best

Linear search finds the target on step 1 at best and step n at worst. Unless stated otherwise, Big-O means the worst case — the guarantee.

Nested loops multiply

A loop inside a loop over the same input runs n × n times: O(n²). Sequential loops add: O(n) + O(n) = O(n).

Halving means log

Any process that cuts the problem in half each step finishes in about log₂(n) steps. log₂(1,000,000) ≈ 20.

Space counts too

Extra memory an algorithm allocates is measured the same way. Recursion uses stack space: depth d costs O(d).

04Build it from scratch

A clean reference implementation. Read it line by line — then close it and write your own in the lab below.

typescript

// Three ways to answer "does this array contain a duplicate?"

// O(n²) time, O(1) space — compare every pair
function hasDuplicateBrute(nums: number[]): boolean {
  for (let i = 0; i < nums.length; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[i] === nums[j]) return true;
    }
  }
  return false;
}

// O(n log n) time — sort, then duplicates sit next to each other
function hasDuplicateSorted(nums: number[]): boolean {
  const sorted = [...nums].sort((a, b) => a - b);
  for (let i = 1; i < sorted.length; i++) {
    if (sorted[i] === sorted[i - 1]) return true;
  }
  return false;
}

// O(n) time, O(n) space — trade memory for speed with a set
function hasDuplicateSet(nums: number[]): boolean {
  const seen = new Set<number>();
  for (const n of nums) {
    if (seen.has(n)) return true;
    seen.add(n);
  }
  return false;
}

05Complexity

Operation	Time
O(1) — constant	array index, hash lookup	—
O(log n) — logarithmic	binary search, balanced tree	—
O(n) — linear	single loop, linear search	—
O(n log n) — linearithmic	merge sort, heap sort	—
O(n²) — quadratic	nested loops, bubble sort	—
O(2ⁿ) — exponential	naive recursive Fibonacci, all subsets	—

06Check your understanding

07Code lab

Write Python(or switch to JavaScript) and run it against real test cases. Python runs inside your browser — nothing is uploaded — and a C++ reference solution is under “Solution”.

Sum 1..n in O(1)

Write sum_to(n) that returns 1 + 2 + … + n without a loop. A loop is O(n); the goal is constant time. Return 0 for n ≤ 0.

function: sum_toPython starts when you get here

⌘/Ctrl + Enter

Two Indexes, One Loop How to Read a Problem