The complexity classes

There are seven Big-O classes that cover almost all the algorithms you will ever write or see. Here they are in order from fastest (least cost) to slowest (most cost):

O(1) — Constant time The algorithm does the same number of operations no matter how big the input is. One lookup, one check, done. It scales like a flat line. For n = 1,000,000: still 1 operation.

Code shape: Direct access, no loops.

function getFirst(array) {
  return array[0];  // O(1)
}

O(log n) — Logarithmic time The algorithm divides the problem in half at each step (binary search, divide-and-conquer). Log₂ of 1,000,000 is about 20, so this is very fast even for huge inputs. For n = 1,000,000: about 20 operations.

Code shape: Divide the search space in half each iteration.

function binarySearch(numbers, target) {
  let left = 0, right = numbers.length - 1;
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    if (numbers[mid] === target) return mid;
    if (numbers[mid] < target) left = mid + 1;
    else right = mid - 1;
  }
  return -1;  // O(log n)
}

O(n) — Linear time The algorithm touches each item once. For n = 1,000,000: 1,000,000 operations. This is practical for almost any input size.

Code shape: Single loop over the input.

function sumAll(numbers) {
  let sum = 0;
  for (let num of numbers) {
    sum += num;
  }
  return sum;  // O(n)
}

O(n log n) — Linearithmic time The algorithm sorts or divides-and-conquers in a clever way. For n = 1,000,000: 1,000,000 × 20 ≈ 20,000,000 operations. Still practical; this is the cost of most efficient sorting algorithms (merge sort, quicksort).

Code shape: Often a single loop that does O(log n) work per iteration, or a divide-and-conquer algorithm.

// Merge sort does O(n log n) work total
function mergeSort(numbers) {
  if (numbers.length <= 1) return numbers;
  const mid = Math.floor(numbers.length / 2);
  const left = mergeSort(numbers.slice(0, mid));
  const right = mergeSort(numbers.slice(mid));
  return merge(left, right);  // O(n log n)
}

O(n²) — Quadratic time Nested loops: for each item, you touch all other items. For n = 1,000,000: 1 trillion operations. Only practical for small inputs (up to a few thousand items).

Code shape: Nested loops.

function allPairs(numbers) {
  for (let i = 0; i < numbers.length; i++) {
    for (let j = i + 1; j < numbers.length; j++) {
      console.log(numbers[i], numbers[j]);
    }
  }  // O(n²)
}

O(2ⁿ) — Exponential time For each additional item, the operations double. For n = 20: 1 million operations. For n = 30: 1 billion. For n = 40: 1 trillion. Only practical for very small inputs (n ≤ ~30).

Code shape: Recursive exploration of all subsets or combinations.

function fibonacci(n) {
  if (n <= 1) return n;
  return fibonacci(n - 1) + fibonacci(n - 2);  // O(2ⁿ) — creates an exponential tree
}

O(n!) — Factorial time For each additional item, the operations multiply: 1, 2, 6, 24, 120, 720, … . For n = 10: 3,600,000 operations. For n = 12: 480,000,000 operations. Only practical for tiny inputs (n ≤ ~10).

Code shape: Generate and check all permutations.

function allPermutations(items) {
  if (items.length <= 1) return [items];
  const result = [];
  for (let i = 0; i < items.length; i++) {
    const rest = items.slice(0, i).concat(items.slice(i + 1));
    for (let perm of allPermutations(rest)) {
      result.push([items[i], ...perm]);
    }
  }
  return result;  // O(n!)
}

These seven classes form the main spectrum. Some algorithms fall in between (O(n^1.5), O(n²log n)), but the seven above are the ones you will see most often.