Big-O Notation

Big-O notation answers one question: as the input grows, how does the work grow? It deliberately ignores hardware speed, compiler tricks, and exact instruction counts. What remains is the shape of the growth — and that shape is what determines whether code survives at scale.

What Big-O Is Not

Big-O does not tell you “this function takes 3 ms”. It tells you that if you double the input, the function might take twice as long (O(n)), or the same amount of time (O(1)), or four times as long (O(n²)). Runtime in milliseconds depends on hardware. Growth shape depends on the algorithm.

Counting Operations

Here is a function that sums an array:

function sum(arr) {
  let total = 0;           // 1 operation
  for (let i = 0; i < arr.length; i++) {  // n iterations
    total += arr[i];       // 1 operation per iteration
  }
  return total;            // 1 operation
}

Total operations: 1 + n + 1 = n + 2.

Dropping Constants and Lower-Order Terms

Big-O keeps only the dominant term as n approaches infinity:

• n + 2 → O(n) (the constant 2 becomes noise at large n)
• 3n + 100 → O(n) (constant factor 3 doesn’t change the shape)
• n² + n → O(n²) (n becomes negligible next to n²)
• 5 → O(1) (constant no matter what n is)

The rule: drop constants, keep the highest-power term.

A Two-Loop Example

function printPairs(arr) {
  for (let i = 0; i < arr.length; i++) {      // n
    for (let j = 0; j < arr.length; j++) {    // n per i
      console.log(arr[i], arr[j]);
    }
  }
}

The inner loop runs n times for each of the n outer iterations: n × n = n². This is O(n²). Every extra nesting level multiplies by n.

Best, Average, and Worst Case

Big-O most commonly describes the worst case — the guarantee you can give regardless of input shape. For example, searching an unsorted array:

• Best case: the target is the first element → O(1)
• Average case: roughly halfway through → O(n/2) = O(n)
• Worst case: target is last or missing → O(n)

When someone says “linear search is O(n)” they mean worst case unless stated otherwise.

Deriving O(n) Step by Step

function containsDuplicate(arr) {
  const seen = new Set();
  for (let i = 0; i < arr.length; i++) {
    if (seen.has(arr[i])) return true;   // Set.has is O(1)
    seen.add(arr[i]);                    // Set.add is O(1)
  }
  return false;
}

Each loop iteration does O(1) work (Set.has and Set.add are hash-based). The loop runs at most n times. Total: O(n).

Using a nested loop to find duplicates would be O(n²). Picking the right data structure dropped a full complexity class.

Up Next

O(n) and O(n²) are two points on a spectrum. The next lesson maps out every class you will encounter and what each means for real input sizes.