Big-O Notation

Big-O notation is the standard language engineers use to describe how an algorithm’s runtime or memory usage grows as the input size grows. It doesn’t tell you how many milliseconds something takes — it tells you the shape of growth. An O(n) algorithm that takes 1 ms for 1,000 items will take roughly 1,000 ms for 1,000,000 items. An O(n²) algorithm that takes 1 ms for 1,000 items will take roughly 1,000,000 ms for the same input. That difference is what Big-O captures.

Why “Big-O”?

The “O” stands for “Order of” — as in, the order of magnitude of growth. We always analyze the worst case unless stated otherwise, and we drop constants and lower-order terms because we only care about behavior at large scale.

Rules:

Drop constants — O(2n) → O(n)
Drop lower-order terms — O(n² + n) → O(n²)
Different inputs get different variables — a loop over array A and a loop over array B is O(a + b), not O(n)

NOTE

Big-O describes an upper bound on growth. Technically O(n) is also O(n²), but we always use the tightest bound that’s accurate.

Common Complexity Classes

Complexity	Name	Example
O(1)	Constant	Array index lookup, hash map get
O(log n)	Logarithmic	Binary search, balanced BST lookup
O(n)	Linear	Single loop over input
O(n log n)	Linearithmic	Merge sort, heap sort
O(n²)	Quadratic	Nested loops over same input
O(2ⁿ)	Exponential	Recursive Fibonacci (naive)
O(n!)	Factorial	Generating all permutations

Code Comparison

// O(1) — constant time, no matter how big `arr` is
function getFirst(arr: number[]): number {
  return arr[0];
}

// O(n) — visits every element once
function linearSearch(arr: number[], target: number): number {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === target) return i;
  }
  return -1;
}

// O(n²) — nested loop, each element paired with every other
function hasDuplicate(arr: number[]): boolean {
  for (let i = 0; i < arr.length; i++) {
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[i] === arr[j]) return true;
    }
  }
  return false;
}

// O(n) — same duplicate check but using a Set
function hasDuplicateFast(arr: number[]): boolean {
  const seen = new Set<number>();
  for (const num of arr) {
    if (seen.has(num)) return true;
    seen.add(num);
  }
  return false;
}

TIP

When you see a nested loop, your first instinct should be O(n²) — but double check whether the inner loop shrinks based on the outer index. Loops with different bounds (i to n, j to i) are still O(n²) on average.

Space Complexity

Space complexity follows the same notation but measures memory allocation instead of time. The hasDuplicateFast function above is O(n) in space (the Set grows with input) whereas hasDuplicate is O(1) in space (no extra data structures). There is often a time-space tradeoff: you can speed things up by using more memory, or save memory by doing more work.

IMPORTANT

Space complexity counts extra space used by your algorithm, not the space for the input itself (which is already given).

Further Learning

Search these terms to go deeper:

“Big-O cheat sheet bigocheatsheet.com” — quick reference table of common algorithms and data structures
“CS50 asymptotic notation lecture” — Harvard’s clear visual walkthrough with growing animations
“Big-O notation practice problems geeksforgeeks” — exercises to classify code snippets
“CLRS Introduction to Algorithms chapter 3” — the definitive textbook treatment of asymptotic notation
“Back to Back SWE Big-O YouTube” — well-paced video covering all the major complexity classes

Big-O Notation

Imagine two ways to find a friend’s name in a phone book. One: read every name from the start. Two: flip to the middle, decide which half to keep, repeat. For a 10-name book both feel instant — but for a million names, one takes forever and the other takes ~20 flips. Big-O is how we describe that difference: not how fast code is, but how its work grows as the input gets bigger.

What Big-O is really saying

Big-O answers: “If I give this code 10× more data, how much more work does it do?” That’s what matters — code that’s fine with 100 items can freeze with 100,000 if it grows badly.

The classes you’ll actually meet

From best to worst:

Big-O	Nickname	Feels like	Example
O(1)	Constant	Instant, always	Grabbing `arr[0]`
O(log n)	Logarithmic	Barely grows	Binary search (halving)
O(n)	Linear	Grows steadily	Looping through a list once
O(n log n)	—	A bit worse than linear	Good sorting algorithms
O(n²)	Quadratic	Grows painfully	A loop inside a loop

Rough intuition: O(1) never cares about size, O(n) doubles when the data doubles, and O(n²) quadruples when the data doubles — that’s the danger zone.

Reading it in code

// O(1) — one step, no matter the size
function first(arr) { return arr[0] }

// O(n) — looks at each item once
function search(arr, target) {
  for (const x of arr) if (x === target) return true
  return false
}

// O(n²) — a loop inside a loop → work explodes
function hasDuplicate(arr) {
  for (let i = 0; i < arr.length; i++)
    for (let j = i + 1; j < arr.length; j++)
      if (arr[i] === arr[j]) return true
  return false
}

TIP

See a loop inside a loop over the same data? That’s almost always O(n²) — a red flag for large inputs. There’s often a faster O(n) way (like using a Set to spot duplicates).

Time vs. space

Big-O also describes memory (space complexity), not just speed. Sometimes you can trade one for the other: use extra memory (a lookup table) to go faster, or use less memory by doing more work.

The two simplification rules

Ignore constants: O(2n) is just O(n). We care about the shape, not exact counts.
Keep only the biggest term: O(n² + n) is just O(n²), because at large sizes the n² dwarfs everything.

In one sentence

Big-O describes how an algorithm’s work grows with input size — aim for O(1), O(log n), or O(n), and be suspicious of nested loops that make it O(n²).

Want to go deeper?

Switch to Expert mode above for the full complexity table (including O(2ⁿ) and O(n!)), worst-case analysis, and more code comparisons.