Skip to content
Velloreth
Programming 6 min read

Big-O Notation Explained With Real Code Examples

Big-O notation describes how an algorithm's cost grows as input grows. Learn the common classes, how to read them, and the mistakes beginners make.

By

What Big-O notation actually measures

Big-O notation describes how the cost of an algorithm grows as its input grows. It is not a stopwatch. It does not tell you how many milliseconds something takes. It tells you the shape of the relationship between input size and work done.

That distinction matters because it is what makes Big-O useful. A measurement in milliseconds is true only for one machine, one language, and one input. A growth rate is true everywhere.

Formally, we say an algorithm is O(f(n)) if there exist constants c and n₀ such that for all n greater than n₀, the running time is at most c × f(n). In practice you never compute those constants. You read the code, count how the work scales, and drop everything except the fastest-growing term.

The common complexity classes

These are the classes you will meet in real code, ordered from best to worst.

ClassNameDoubling n multiplies work byTypical source
O(1)Constant1× (unchanged)Array index, hash lookup
O(log n)Logarithmic~1× plus a constantBinary search, balanced tree
O(n)Linear2×Single pass over a list
O(n log n)Linearithmic~2× plus a bitEfficient sorting
O(n²)Quadratic4×Nested loops over the same input
O(2ⁿ)ExponentialSquaredNaive subset enumeration

The gap between these is not academic. At n = 1,000,000, an O(n log n) sort does roughly 20 million operations while an O(n²) sort does a trillion. That is the difference between a page that loads and a page that times out.

Reading complexity from code

The skill is recognising which part of your code scales with the input.

Constant time: O(1)

function firstItem(items) {
  return items[0];
}

No matter how long items is, this does one thing. Array indexing is O(1) because the element’s address is computed directly from the index.

Hash map lookups are also O(1) on average:

const seen = new Map();
seen.set('key', 1);
seen.get('key'); // O(1) average

The “average” qualifier matters. A hash map degrades to O(n) per lookup in the worst case when many keys collide, which is why a good hash function and a sensible load factor matter.

Linear time: O(n)

function sum(numbers) {
  let total = 0;
  for (const n of numbers) total += n;
  return total;
}

One pass, one operation per element. Double the array, double the work.

Quadratic time: O(n²)

function hasDuplicatePairs(items) {
  for (let i = 0; i < items.length; i++) {
    for (let j = i + 1; j < items.length; j++) {
      if (items[i] === items[j]) return true;
    }
  }
  return false;
}

The outer loop runs n times, and for each iteration the inner loop runs roughly n times. That is n × n = n².

The same problem in O(n) with a set:

function hasDuplicatePairs(items) {
  const seen = new Set();
  for (const item of items) {
    if (seen.has(item)) return true;
    seen.add(item);
  }
  return false;
}

This is the single most common performance win available to a working developer: replacing a nested loop with a hash-based lookup.

Logarithmic time: O(log n)

function binarySearch(sorted, target) {
  let low = 0;
  let high = sorted.length - 1;
  while (low <= high) {
    const mid = Math.floor((low + high) / 2);
    if (sorted[mid] === target) return mid;
    if (sorted[mid] < target) low = mid + 1;
    else high = mid - 1;
  }
  return -1;
}

Each iteration halves the search space. Starting from a million elements, you reach one in about 20 steps, because 2²⁰ ≈ 1,000,000. That is what makes binary search so much better than scanning.

The mistakes beginners make

Assuming nested loops always mean O(n²). They mean O(n²) only when both loops scale with the same input. This is O(n):

for (const word of words) {
  for (const letter of 'abcdefghijklmnopqrstuvwxyz') {
    // 26 iterations, always
  }
}

The inner loop is bounded by a constant, so it collapses into the outer loop’s cost.

Forgetting that built-in methods have costs. Array.prototype.includes is O(n). Calling it inside a loop gives you O(n²) without a single nested for:

// O(n²) — includes() scans the array every time
for (const id of ids) {
  if (otherIds.includes(id)) { /* ... */ }
}

// O(n) — one set, then constant-time lookups
const otherSet = new Set(otherIds);
for (const id of ids) {
  if (otherSet.has(id)) { /* ... */ }
}

Confusing time and space. Big-O applies to memory too. A function that builds a set of every element is O(n) space. That is usually a fine trade, but it is a trade, and on a memory-constrained device it can be the wrong one.

Optimising the wrong thing. Big-O describes asymptotic behaviour. If your input is always 20 items, an O(n²) algorithm is not your problem — your problem is the network request, the database query, or the render. Measure before you rewrite.

Amortised complexity

Some operations are occasionally expensive but cheap on average. Appending to a dynamic array is the classic case.

const arr = [];
for (let i = 0; i < 1_000_000; i++) arr.push(i);

Most push calls are O(1). But when the array’s capacity is exhausted, the runtime allocates a larger block and copies everything over — an O(n) operation. Because the capacity doubles each time, those expensive copies happen at exponentially increasing intervals, and the total cost across n appends works out to O(n). So each append is O(1) amortised.

This is why push is not a performance concern, and why the same reasoning makes hash map insertion O(1) amortised.

How to use this in practice

You do not need to annotate every function. You need to notice the cases where growth will bite:

  • Loops inside loops over the same collection — the classic quadratic trap.
  • Linear scans inside loops — includes, indexOf, find on arrays.
  • Repeated work that could be cached — recomputing the same value per iteration.
  • Recursion without memoisation — naive Fibonacci is O(2ⁿ); with memoisation it is O(n).

When you find one, the fix is usually a hash map or set, a sort plus a single pass, or a cache. Those three moves resolve the large majority of real-world complexity problems.

If you want to go deeper on the structures that make these trade-offs possible, data structures every developer should know covers the practical set, and time vs space complexity explains the trade-off you are actually making. For the recursive case specifically, understanding recursion with practical examples walks through why naive recursion explodes and how memoisation fixes it.

Quotable summary

Big-O notation describes the growth rate of an algorithm’s cost as input size increases, discarding constant factors and lower-order terms. The classes you meet in practice, from best to worst, are O(1), O(log n), O(n), O(n log n), O(n²), and O(2ⁿ). Nested loops over the same input produce O(n²); replacing them with a hash-based lookup usually produces O(n). Big-O is a property of the algorithm, not the machine, which is why it is the right tool for reasoning about scale — and the wrong tool for reasoning about small inputs, where constants dominate.

Frequently asked questions

What is Big-O notation in simple terms?
Big-O notation is a way of describing how much slower an algorithm gets as you give it more data. It ignores constant factors and focuses on the shape of the growth curve, so O(n) means doubling the input roughly doubles the work, while O(n²) means doubling the input quadruples it.
What is the difference between Big-O, Big-Omega, and Big-Theta?
Big-O is an upper bound on growth, Big-Omega is a lower bound, and Big-Theta is a tight bound that holds in both directions. In everyday engineering conversation people say Big-O but usually mean Big-Theta, the tight description of how the algorithm scales.
Is O(1) always faster than O(n)?
No. Big-O ignores constant factors, so an O(1) operation with a large constant can be slower than an O(n) loop for small n. Big-O tells you what happens as n grows large, which is usually but not always the regime that matters.
Why does Big-O ignore constants?
Because constants depend on the machine, the language, and the compiler, while the growth rate is a property of the algorithm itself. Dropping constants makes Big-O portable: it describes the algorithm, not the hardware it happens to run on.
What is the time complexity of a nested loop?
Two loops nested over the same input of size n give O(n²), because the inner loop runs n times for each of the n outer iterations. If the inner loop runs over a fixed-size collection instead, the complexity stays O(n).
Does Big-O matter for small inputs?
Rarely. For inputs of a few dozen elements, constant factors and cache behaviour usually dominate, and a simpler O(n²) algorithm can be faster and easier to read. Big-O matters when input size is unbounded or already large.