Big O Notation Explained with Real Examples

"O(n)" is easy to recite and surprisingly hard to spot in a function you didn't write five minutes ago. This is the code-first companion to Algorithm Complexity Explained — that post covers the formal definitions of O, Θ, and Ω and how best/worst/average case fits in; this one skips straight to real snippets and teaches the habit of reading a function and naming its growth rate on sight.

The habit: count the loops, not the syntax

The fastest way to estimate a function's time complexity is to ask one question: for an input of size n, how many times does the "hot" line of code actually run?

• No loop, or a loop that doesn't depend on n — constant work. O(1).
• One loop over n items — O(n).
• A loop that throws away half the remaining work each time — O(log n).
• A loop over n items, where each iteration itself does O(n) work — O(n²). This is true whether that inner O(n) work is a visually nested loop or a single innocent-looking function call — the syntax doesn't matter, only how much work each call actually does.
• A function that calls itself twice for every one call, without caching — O(2ⁿ).

That last point about the O(n²) case is the one that catches people — a single for loop with no nesting in sight can still be O(n²) if the line inside it isn't actually O(1). The examples below make that concrete.

O(1) — Constant time

Work that doesn't grow no matter how large the input gets:

const first = arr[0];        // array index access
const size = arr.length;     // tracked, not counted
const user = userMap.get(id); // hash map lookup — average case
arr.push(newItem);            // amortized — see note below

Array indexing is O(1) because arrays are laid out so the address of arr[i] can be computed directly from i — no searching required. Map and Set lookups are O(1) on average (hash-based — formally this is an average-case guarantee, not a worst-case one, in the same sense covered in Algorithm Complexity Explained). Appending with push is usually described as amortized O(1): most calls are cheap, and the occasional internal resize is expensive but rare enough that its cost, spread out over every call, averages out to constant.

The practical payoff: if you're checking whether a value exists in a collection more than once, a Set almost always beats an array.

arr.includes(value);   // O(n) — scans until it finds a match or reaches the end
set.has(value);         // O(1) average — direct hash lookup, no scanning

O(log n) — Logarithmic time

Binary search is the canonical example — it only works on a sorted array, because that's what lets it discard half the remaining range on every comparison instead of checking each element:

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

A search space of 1,000,000 sorted elements takes at most 20 comparisons this way — each comparison halves what's left, so it takes log₂(1,000,000) ≈ 20 halvings to get down to one element. Search Algorithm Visualizer runs this exact loop step by step next to plain Linear Search on the same array, with the shrinking low/high range visible at every comparison.

O(n) — Linear time

Work that grows exactly proportionally to the input size — every element gets touched once:

let total = 0;
for (const price of prices) {
  total += price;           // O(n) — one pass
}

prices.includes(19.99);      // O(n) — scans until found or exhausted
prices.find(p => p > 100);   // O(n) — same shape, different early-exit condition
Math.max(...prices);         // O(n) — has to look at every element to know the max

All four of these look different but do the same amount of structural work: one pass over n items, with a constant amount of work per item.

O(n log n) — Linearithmic time

This is the complexity class of efficient general-purpose sorting. Modern JavaScript engines (V8, which runs Chrome and Node.js) use Timsort for Array.prototype.sort — the same hybrid merge/insertion algorithm covered in Algorithm Complexity Explained, which is where the O(n log n) guarantee for sorting an array of any real size comes from:

const sorted = [...prices].sort((a, b) => a - b); // O(n log n)

The log n factor comes from repeatedly splitting the array in half (like binary search) — merge sort splits the whole array down to single elements (log n levels of splitting) and then merges each level back together, touching all n elements at every level:

function mergeSort(arr) {
  if (arr.length <= 1) return arr;
  const mid = Math.floor(arr.length / 2);
  const left = mergeSort(arr.slice(0, mid));   // log n levels of splitting
  const right = mergeSort(arr.slice(mid));
  return merge(left, right);                   // n work merging, at every level
}

Sorting Algorithm Visualizer runs Merge Sort exactly like this, step by step, alongside five other algorithms on the same array.

O(n²) — Quadratic time

A loop nested inside another loop, both scaling with the input, does roughly n × n units of work:

function hasDuplicatePair(nums) {
  for (let i = 0; i < nums.length; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[i] === nums[j]) return true; // checked against every other element
    }
  }
  return false;
}

An 8-element input touches 8 cells with one loop and 64 with two nested ones — that gap doesn't stay small. Big O Calculator shows the exact operation counts at whatever size you actually care about, and Sorting Algorithm Visualizer makes O(n²) directly visible — watch Bubble Sort or Quick Sort (on an already-sorted array) do it in real time.

The version of this that actually catches people in review isn't visually nested:

function findCommonItems(listA, listB) {
  return listA.filter(item => listB.includes(item)); // one loop... that hides another
}

There's only one visible for-shaped construct here (filter), but listB.includes(item) is itself an O(n) scan, called once per element of listA. That's O(n) calls to an O(n) operation — O(n²) total, with no nested braces anywhere in sight. Swapping listB for a Set and calling .has() instead turns this into O(n) overall — same output, same overall shape of the code, one data-structure swap away from a completely different growth class. See When O(n²) Becomes a Problem for exactly how much that swap is worth as the input grows — the same fix, with real numbers.

O(2ⁿ) — Exponential time

Naive recursive Fibonacci is the standard example — and it's worse than it looks:

function fib(n) {
  if (n <= 1) return n;
  return fib(n - 1) + fib(n - 2); // two calls, for every one call
}

Every call that isn't a base case makes two more calls, and neither call knows the other one might be about to recompute the exact same value. fib(15) alone makes 1,973 calls to compute a single number — verified by actually running the trace in Recursion vs Iteration Visualizer, which also shows what changes with memoization: caching each result the first time it's computed drops the same call to 29 calls, turning O(2ⁿ) into O(n) by trading a small amount of memory for an exponential amount of avoided work.

Cheat sheet: code pattern → complexity

Try it yourself

Big O Calculator and Complexity Visualizer turn every class in this post into exact operation counts and growth curves at whatever input size you plug in, and Algorithm Runtime Estimator converts an operation count into actual estimated runtime — the moment an O(n²) function stops being a theoretical concern and starts being a support ticket. All of the tools linked throughout this post run entirely in your browser.

FAQ

Is Array.prototype.sort really O(n log n) for every case?

For a comparator-based sort of general data, yes. Specialized cases can beat it — sorting a small, known range of integers can be done in O(n) with counting sort, for instance — but that's a different algorithm entirely, not a faster general-purpose comparison sort. See Algorithm Complexity Explained for why Ω(n log n) is a proven floor for any comparison-based sort.

Why does the order of operations inside a loop matter?

Because the loop's complexity is the loop count multiplied by whatever runs inside it, not just the loop count on its own. An O(n) loop containing an O(1) operation is O(n). The exact same O(n) loop containing an O(n) operation — a nested loop, an includes(), a find() — is O(n²). The loop itself never changed; what's inside it did.

Do I need to count exactly? Two loops in a row, or one after another?

Two separate, non-nested loops over the same input add: O(n) + O(n) = O(2n), which simplifies to O(n) — the constant factor of 2 is exactly the kind of detail Big O deliberately throws away, as covered in Algorithm Complexity Explained. Nesting is what multiplies; sequencing just adds.

How does this apply in a coding interview?

Exactly this way — interviewers want the same causal reasoning shown here (this loop runs n times, this call inside it is O(n), so O(n²) overall), applied out loud to whatever you've just written. See Time Complexity Interview Guide for a framework for stating it and the data-structure complexities worth having memorized.