The complexity classes you will actually meet

Seven growth rates, what produces each one, and where the cliff edges are.

Lesson 8 of 75 · Beginner 2 min read

Almost everything you write falls into one of seven classes. Learn what causes each one and you can read complexity off the shape of the code.

Class	Name	Caused by	n = 1,000,000
O(1)	Constant	Direct index, hash lookup, arithmetic	1
O(log n)	Logarithmic	Halving the search space each step	~20
O(n)	Linear	One pass over the input	1,000,000
O(n log n)	Linearithmic	Sorting; divide and conquer with linear merging	~20,000,000
O(n²)	Quadratic	Nested loops over the same input	10¹²
O(2ⁿ)	Exponential	Trying both choices at every step	beyond hopeless
O(n!)	Factorial	Generating every permutation	beyond hopeless

The cliff edges

Between O(n log n) and O(n²) is the line that separates code that scales from code that does not. Above O(n²), inputs must be tiny: O(2ⁿ) is fine at n = 20 and impossible at n = 60.

Recognising them in code

arr[i];                                   // O(1)

while (n > 1) n = Math.floor(n / 2);      // O(log n) — n halves

for (const x of arr) { }                  // O(n)

arr.sort((a, b) => a - b);                // O(n log n)

for (const a of arr) for (const b of arr) { }   // O(n²)

function subsets(i) {                     // O(2ⁿ) — two branches, depth n
  if (i === arr.length) return;
  subsets(i + 1);                         // exclude
  subsets(i + 1);                         // include
}

Reading the constraints

Interview and contest problems tell you the target complexity through the input limit:

Limit on n	Expected solution
n ≤ 20	Exponential is fine — backtracking, bitmask
n ≤ 5,000	O(n²)
n ≤ 10⁵ or 10⁶	O(n log n) or O(n)
n ≥ 10⁹	O(log n) or O(1) — maths, not iteration

Read the constraint first. It often names the algorithm before you have thought about the problem.