Big O notation

Overview

Big O notation describes how the running time or memory of an algorithm grows as the input size n grows. It ignores machine speed and constant factors, and keeps only the term that dominates for large n. An algorithm that does 3n + 20 steps is O(n); one that does n^2 / 2 + 5n steps is O(n^2).

Big O lets you compare solutions before writing them and predict whether they will pass. With n = 100,000, an O(n^2) solution does about 10 billion operations and will time out, while O(n log n) does about 1.7 million and finishes instantly. Reading constraints and choosing the right target complexity is the first skill of problem solving.

When to use it

• Comparing two approaches to the same problem before coding.
• Reading problem constraints to decide which complexity will pass (see the table below).
• Explaining in an interview why your optimized solution is better than brute force.
• Predicting how a production endpoint behaves when data grows 10x or 100x.

Problem patterns it solves

Where it is used in real software

Key terms

n

The size of the input: array length, number of nodes, string length, or the numeric value itself.

Big O (upper bound)

Growth is at most proportional to f(n) for large n. Used for worst-case guarantees.

Big Omega (lower bound)

Growth is at least proportional to f(n). Example: comparison sorting is Omega(n log n).

Big Theta (tight bound)

Growth is exactly proportional to f(n), both upper and lower bound.

Dominant term

The fastest-growing term. In n^2 + 100n + 7, n^2 dominates for large n.

Amortized

Average cost per operation over a long sequence, even if some single operations are expensive.

How to find the Big O of any code

1. 1
   Define n

   Decide what grows: the array length, the number of nodes, or both (use n and m separately for two inputs).

2. 2
   Count the work of each block

   A simple statement is O(1). A loop that runs n times multiplies the work of its body by n.

3. 3
   Multiply for nesting, add for sequence

   A loop inside a loop is O(n x n) = O(n^2). Two separate loops one after the other are O(n + n) = O(n).

4. 4
   Watch for hidden loops

   Array.includes, indexOf, slice, splice, string concatenation in a loop, and list.remove(0) are all O(n) themselves.

5. 5
   Drop constants and smaller terms

   O(2n) becomes O(n); O(n^2 + n) becomes O(n^2); O(n / 2) becomes O(n).

6. 6
   Keep independent inputs separate

   Looping over array a then array b is O(a + b), not O(n). Nested over both is O(a x b).

How fast each complexity grows

Approximate operation counts. A typical judge runs about 10^8 simple operations per second.

O(log n) barely moves, O(n) and O(n log n) stay practical up to millions, O(n^2) becomes too slow around 10^5, and O(2^n) is only usable for n around 20 to 25.

Implementation

1// O(1): same work regardless of n2function first(arr) {3  return arr[0];4}5 6// O(n): touches each element once7function sum(arr) {8  let total = 0;9  for (const x of arr) total += x;10  return total;11}12 13// O(n^2): every pair14function hasDuplicateSlow(arr) {15  for (let i = 0; i < arr.length; i++) {16    for (let j = i + 1; j < arr.length; j++) {17      if (arr[i] === arr[j]) return true;18    }19  }20  return false;21}22 23// O(n) time, O(n) space: trade memory for speed24function hasDuplicateFast(arr) {25  const seen = new Set();26  for (const x of arr) {27    if (seen.has(x)) return true;28    seen.add(x);29  }30  return false;31}32 33// O(log n): the range halves every iteration34function countHalvings(n) {35  let steps = 0;36  while (n > 1) {37    n = Math.floor(n / 2);38    steps++;39  }40  return steps;41}42 43// Hidden O(n^2): includes() is itself a loop44function uniqueSlow(arr) {45  const out = [];46  for (const x of arr) if (!out.includes(x)) out.push(x);47  return out;48}

Complexity and performance

Trade-offs

Variants and related techniques

Common mistakes

• Calling an O(n) built-in inside a loop.

  Fix: Know the cost of includes, indexOf, splice, shift, substring, and list.remove(index). Use a Set or Map for repeated lookups.

• Saying O(2n) or O(n + 5).

  Fix: Drop constants: both are O(n).

• Adding when you should multiply.

  Fix: Nested loops multiply; sequential loops add.

• Ignoring string building cost.

  Fix: Repeated s += c in a loop can be O(n^2) in Java. Use StringBuilder, or collect parts in a JS array and join once.

Interview questions

Practice problems