Big-O Notation

Table of Contents

1. What Big-O Actually Says
2. Drop the Constants
3. O(1): Constant Time
4. O(log n): Logarithmic Time
5. O(n): Linear Time
6. O(n log n): Sorting Territory
7. O(n^2): Reading Nested Loops
8. O(2^n): Exponential Time
9. Best, Worst, and Average Case
10. Measuring Real Time
11. includes vs Set.has
12. Linear Search vs Binary Search
13. Space Complexity
14. Recipe: The bench Module
15. Try It Yourself

1. What Big-O Actually Says

Your page loads in a blink with 100 users. With 100,000 users it takes a minute. What changed? Not the code, only the size of the data. Big-O notation is a way to describe how the work of a program grows as the input grows.

It does not tell you how many milliseconds something takes. It tells you the shape of the growth curve, the same shapes from Functions, Growth and Logarithms. Read O(n) as "on the order of n": if the input has n items, the work grows in proportion to n.

Here are the common shapes, from best to worst, with how many steps each needs:

(n^2 means n * n. The log values are rounded up, and n log n is n times log2(n).)

Look at the last column. A million items with an O(n^2) algorithm is a trillion steps, which is hours or days. An O(n log n) algorithm does the same job in a fraction of a second. Choosing the right algorithm matters far more than buying a faster server.

2. Drop the Constants

Big-O keeps only the part that dominates when n gets large, and ignores the rest. Two rules:

1. Drop constant multipliers. If one loop does 3 operations per item and another does 1, both are O(n). 3n and n have the same shape: a straight line.
2. Drop smaller terms. n^2 + n is just O(n^2), because when n = 1,000,000 the n^2 part is a trillion and the extra n is a rounding error.

function example(items) {
  let count = 0;

  for (const a of items) count++;           // n steps
  for (const a of items) count += 2;        // n steps
  for (const a of items) {                  // n * n steps
    for (const b of items) count++;
  }

  return count;
}
// Total: n + n + n*n = n^2 + 2n  ->  O(n^2)

This looks sloppy, and it is on purpose. Constants depend on the machine, the language, and the day. The shape of the curve does not.

One caution: constants do matter in practice when n is small. For 10 items an O(n^2) algorithm with a tiny constant can beat a clever O(n log n) one. Big-O is about what happens as the data keeps growing.

3. O(1): Constant Time

O(1) means the work does not depend on n at all. Reading an array item by its index, looking up a key in an object or Map, or adding two numbers all take about the same time whether the collection has ten items or ten million.

const ids = [101, 102, 103, 104, 105];
console.log(ids[0]);              // 101
console.log(ids[ids.length - 1]); // 105

Both lines are O(1): the computer jumps straight to the position using arithmetic and does not walk through the list. The 1 does not mean "one step". It means "a fixed number of steps".

4. O(log n): Logarithmic Time

O(log n) means each step throws away a big fraction (usually half) of what is left. You met it in the last chapter: binary search.

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;
}

The loop runs log2(n) times because the range low..high halves each time. One million items needs at most 20 loop passes; one billion needs 30. Whenever you see a loop where the remaining problem is cut in half (or by some fixed fraction), think O(log n).

Telltale signs: n = n / 2 inside a loop, or i *= 2 as the loop step.

function countHalvings(n) {
  let count = 0;
  while (n > 1) {
    n = Math.floor(n / 2);
    count++;
  }
  return count;
}

console.log(countHalvings(1_000_000)); // 19
console.log(countHalvings(1024));      // 10

5. O(n): Linear Time

O(n) means you touch every item about once. Double the data, double the work. Summing a list, finding the largest value, or checking whether an array contains something are all linear.

function linearSearch(arr, target) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === target) return i;
  }
  return -1;
}

console.log(linearSearch([40, 10, 30, 20], 30)); // 2
console.log(linearSearch([40, 10, 30, 20], 99)); // -1

In the worst case (the target is last, or missing) it looks at all n items. Many built-ins are linear without telling you: array.includes, array.indexOf, array.find, array.filter, array.map, and array.reduce all walk the array.

A common beginner trap is hiding a linear step inside another loop, which turns O(n) into O(n^2):

// For each order, find its customer: looks like one loop, but .find walks too.
for (const order of orders) {
  const customer = customers.find((c) => c.id === order.customerId);
}

If both lists have n items, that is n * n steps. Build a Map of customers by id once (O(n)), then look each up in O(1), and the whole job becomes O(n).

6. O(n log n): Sorting Territory

O(n log n) is what you get when you do an O(log n) piece of work for each of n items, or split the data in half repeatedly and do linear work at each level. Good general-purpose sorting is the classic example: JavaScript's array.sort() is O(n log n).

const nums = [5, 2, 9, 1, 7];
const sorted = [...nums].sort((a, b) => a - b);
console.log(sorted); // [ 1, 2, 5, 7, 9 ]
console.log(nums);   // [ 5, 2, 9, 1, 7 ] (the original is untouched)

[...nums] makes a copy first, because sort changes the array it is called on. The (a, b) => a - b part is needed for numbers: without it, sort compares items as text, and 10 would sort before 2.

You can see the shape by counting a loop that runs n times with an inner loop that doubles:

function nLogN(n) {
  let count = 0;
  for (let i = 0; i < n; i++) {
    for (let j = 1; j < n; j *= 2) count++;
  }
  return count;
}

console.log(nLogN(1024)); // 10240 (that is 1024 * 10)

O(n log n) is only slightly worse than linear. Sorting a million items takes around 20 million basic steps, which a laptop does in a fraction of a second. It is the price of ordered data, and ordered data is what makes O(log n) binary search possible.

7. O(n^2): Reading Nested Loops

A loop inside a loop, each running over the same n items, gives O(n^2). The inner body runs n * n times:

function countPairs(items) {
  let count = 0;
  for (let i = 0; i < items.length; i++) {
    for (let j = 0; j < items.length; j++) {
      count++;
    }
  }
  return count;
}

console.log(countPairs([1, 2, 3, 4, 5]));      // 25
console.log(countPairs(new Array(10).fill(0))); // 100

Doubling the input quadruples the work: 5 items gave 25, 10 items gave 100. Here is a quick guide to reading loops:

There is a common variant where the inner loop starts after the outer one (j = i + 1), as when checking every pair for a duplicate:

function countUniquePairs(n) {
  let count = 0;
  for (let i = 0; i < n; i++) {
    for (let j = i + 1; j < n; j++) {
      count++;
    }
  }
  return count;
}

console.log(countUniquePairs(5));   // 10
console.log(countUniquePairs(100)); // 4950

That runs n * (n - 1) / 2 times, which for n = 100 is 4,950. It is about half of n^2, but halves are constants, so it is still O(n^2).

A practical example is finding duplicates. This version compares every pair:

function hasDuplicateSlow(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;
}

This one remembers what it has seen in a Set, and is O(n):

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

You trade memory for time. We will measure both in a moment. (The Set type comes straight from Sets and Set Operations.)

8. O(2^n): Exponential Time

O(2^n) doubles the work for every extra item. It usually appears when code tries every combination or recurses twice per call. The naive fib from the last chapter is one example. Another is generating every subset of a list:

function subsets(items) {
  if (items.length === 0) return [[]];
  const [first, ...rest] = items;
  const without = subsets(rest);
  const with_ = without.map((s) => [first, ...s]);
  return [...without, ...with_];
}

console.log(subsets([1, 2, 3]).length);       // 8
console.log(subsets([1, 2, 3, 4]).length);    // 16
console.log(subsets([1, 2, 3]));
// [ [], [ 3 ], [ 2 ], [ 2, 3 ], [ 1 ], [ 1, 3 ], [ 1, 2 ], [ 1, 2, 3 ] ]

For n items there are 2^n subsets. Thirty items give over a billion; sixty items could not be finished in your lifetime. If a task seems to need O(2^n), look for a smarter approach (such as remembering earlier answers) or accept an approximate result.

A related, even worse shape is O(n!), such as trying every ordering of n items. You will meet it in Counting: Permutations and Combinations.

9. Best, Worst, and Average Case

The same code can take different effort depending on the data. Take linearSearch:

• Best case: the target is the first item. One step, O(1).
• Worst case: the target is last or missing. n steps, O(n).
• Average case: you look through about half the list, n / 2 steps, which is still O(n) once you drop the constant.

When people say "this is O(n)" without qualification, they almost always mean the worst case. That is the guarantee you can plan around: it will never be worse than this.

Binary search is the same: best case is a hit on the first middle probe (one comparison), the worst case is about log2(n) probes. Even the worst case for one million items is only 20.

10. Measuring Real Time

Big-O is a prediction. To see what really happens, measure. Node gives you two simple tools.

console.time and console.timeEnd print the elapsed time with a label:

const numbers = Array.from({ length: 1_000_000 }, (_, i) => i);

console.time("sum");
let total = 0;
for (const n of numbers) total += n;
console.timeEnd("sum"); // sum: 4.1ms (your number will differ)
console.log(total);     // 499999500000

performance.now() returns a high-resolution timestamp in milliseconds, so you can subtract two readings and use the result in code:

const start = performance.now();
let total = 0;
for (let i = 0; i < 1_000_000; i++) total += i;
const elapsed = performance.now() - start;
console.log(`took ${elapsed.toFixed(2)} ms`); // took 1.30 ms (varies)

Some honest warnings about benchmarks:

• Timings vary from machine to machine, and even from run to run. Trust the ratio between two measurements, not the exact numbers.
• The first run is often slower while the engine warms up. Repeat the work and look at several runs.
• Very fast operations need to be repeated (say 100 or 1,000 times) to produce a number larger than the timer's noise.
• Measure realistic data sizes. Small inputs hide the difference between growth shapes.

11. includes vs Set.has

Does array.includes(x) look every item? Yes: it is O(n). Does set.has(x) look every item? No: a Set is built on a hash table and answers in about O(1) on average. Let us test with a million items, searching for the last one, 100 times:

const arr = Array.from({ length: 1_000_000 }, (_, i) => i * 2);
const set = new Set(arr);
const target = arr[arr.length - 1]; // worst case for the array

let start = performance.now();
for (let i = 0; i < 100; i++) arr.includes(target);
console.log("includes:", (performance.now() - start).toFixed(2), "ms");

start = performance.now();
for (let i = 0; i < 100; i++) set.has(target);
console.log("Set.has: ", (performance.now() - start).toFixed(4), "ms");
// includes: 14.20 ms
// Set.has:  0.0268 ms   (numbers will differ on your machine)

On a typical laptop the Set is hundreds of times faster here, and the gap widens as the collection grows. The array did 100 passes over a million items; the Set did 100 quick lookups.

The trade-off: building the Set costs time and memory. If you search once, the array is fine. If you search many times, build the Set once. That is exactly how a permission checker or a "have I seen this ID?" filter should work.

The same idea explains the duplicate-checker from earlier:

const small = Array.from({ length: 20_000 }, (_, i) => i);

let t = performance.now();
hasDuplicateSlow(small);
console.log("slow:", (performance.now() - t).toFixed(1), "ms"); // about 75 ms

t = performance.now();
hasDuplicateFast(small);
console.log("fast:", (performance.now() - t).toFixed(2), "ms"); // about 1 ms

With 5,000 items the same test took about 4.6 ms for the slow version; with 20,000 items (4 times as many) it took about 16 times as long. That is O(n^2) showing itself in real numbers: 4 times the data, 16 times the time.

12. Linear Search vs Binary Search

Now the race we promised. Take a sorted array of a million even numbers and search for the last element, using both functions (repeated 100 times each so the timings are measurable):

const sorted = Array.from({ length: 1_000_000 }, (_, i) => i * 2);
const target = sorted[sorted.length - 1];

let start = performance.now();
for (let i = 0; i < 100; i++) linearSearch(sorted, target);
const linearMs = performance.now() - start;

start = performance.now();
for (let i = 0; i < 100; i++) binarySearch(sorted, target);
const binaryMs = performance.now() - start;

console.log("linear:", linearMs.toFixed(2), "ms");  // about 60 ms
console.log("binary:", binaryMs.toFixed(4), "ms");  // about 0.1 ms
console.log("binary is faster:", binaryMs < linearMs); // true

Linear search does about a million comparisons per search; binary search does 20. Even though binary search has more complicated code per step, the difference in shape swamps it, and the real timings differ by a factor of several hundred. As always, exact times vary by machine.

You can count the steps to see this without a stopwatch:

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

countingBinarySearch(sorted, target);
console.log(comparisons); // 20

One catch: binary search needs sorted data. Sorting costs O(n log n). If you search a list once, a linear scan is cheaper than sorting first. If you search it thousands of times, sort once.

13. Space Complexity

Time is not the only resource. Space complexity describes how much extra memory your code needs as the input grows, using the same Big-O notation.

Notice the pattern in the duplicate checker: the fast version spends O(n) memory to save time. Many speedups work that way (a cache is this same trade). The decision depends on what is scarce: on a phone with little memory, or with a huge dataset, you may prefer the slower, leaner version.

14. Recipe: The bench Module

Add this chapter's tools to mathlab. Create src/bench.js:

// src/bench.js

// Run fn once and report how long it took.
export function time(fn, label = "task") {
  const start = performance.now();
  const result = fn();
  const ms = performance.now() - start;
  return { label, ms, result };
}

// O(n): look at items one by one.
export function linearSearch(arr, target) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === target) return i;
  }
  return -1;
}

// O(log n): the array must already be sorted ascending.
export 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;
}

time(fn, label) returns an object holding the label, the elapsed milliseconds, and whatever fn returned, so you can print it or compare it. Re-export the module from src/index.js:

export * from "./bench.js";

Add this to demo.js and run node demo.js:

import { time, linearSearch, binarySearch } from "./src/bench.js";

console.log("--- bench ---");
const sorted = Array.from({ length: 1_000_000 }, (_, i) => i * 2);
const last = sorted[sorted.length - 1];
const set = new Set(sorted);

console.log(linearSearch(sorted, last)); // 999999
console.log(binarySearch(sorted, last)); // 999999
console.log(binarySearch(sorted, 7));    // -1 (7 is odd, so it is not in the list)

const linear = time(() => {
  for (let i = 0; i < 100; i++) linearSearch(sorted, last);
}, "linear x100");
const binary = time(() => {
  for (let i = 0; i < 100; i++) binarySearch(sorted, last);
}, "binary x100");
const includes = time(() => {
  for (let i = 0; i < 100; i++) sorted.includes(last);
}, "includes x100");
const setHas = time(() => {
  for (let i = 0; i < 100; i++) set.has(last);
}, "set.has x100");

for (const r of [linear, binary, includes, setHas]) {
  console.log(r.label.padEnd(14), r.ms.toFixed(3), "ms"); // timings vary by machine
}
console.log("binary faster than linear:", binary.ms < linear.ms);   // true
console.log("Set.has faster than includes:", setHas.ms < includes.ms); // true

The three search results and the two true lines are stable; the millisecond numbers are not. On one laptop the four timing lines came out at roughly 62 ms, 0.1 ms, 14 ms, and 0.03 ms. Yours will be different, but the ordering should match.

15. Try It Yourself

1. Classify these. Give the Big-O for each: (a) arr[5]; (b) a single for loop over arr; (c) a for loop over arr with arr.includes(x) inside; (d) a while (n > 1) n = n / 2; (e) arr.sort(...); (f) three nested loops over arr.
2. Drop the constants. Simplify 5n + 20, n^2 + 1000n, and 3 * 2^n + n^5. What does each reduce to?
3. Count the work. Write countTriples(n) with three nested loops, each from 0 to n - 1, that counts iterations. Print it for n = 5 and n = 10. By what factor does the count grow when n doubles?
4. Find the break-even. Time hasDuplicateSlow and hasDuplicateFast on arrays of 100, 1,000, and 10,000 distinct numbers using time from src/bench.js. At which size does the Set version clearly win?
5. Fix the hidden loop. You have orders and customers, each with 1,000 objects. Rewrite the orders loop from section 5 so it builds a Map of customers by id first. Explain in one sentence why it is faster.
6. Binary search step counter. Modify binarySearch to also return how many comparisons it made. Run it on arrays of 10, 1,000, and 1,000,000 sorted items searching for a missing value. Do the counts match Math.ceil(Math.log2(n + 1))?

Where to go next. Big-O is the vocabulary of algorithm design. The planned Data Structures & Algorithms series on this site builds on it: arrays versus hash maps, linked lists, stacks, queues, trees, graphs, sorting, and recursion, always asking "what is the cost?". For now you know enough to spot a quadratic loop in code review.

Big-O answers "how much work?". The next question is "how many possibilities?", which is where combinatorics comes in: Counting: Permutations and Combinations.