Big-O Comparison

The ladder — click a class to show or hide it

try:

Input size n, up to

Operations axis

How many operations is that?

A judge runs roughly 10⁸ simple operations a second. That single number turns a constraint like n ≤ 10⁵ into the complexity the interviewer expects — read the last column backwards. Budget:

fits in ~1 s within 10× — tight, constant factor decides over 10× — times out

Compare two

Which grows faster, are they the same class, and from what n does the difference actually show? Every variable is treated as n.

Read the constraint, guess the algorithm

The fastest way to the intended solution is the bound on n. At ~10⁸ operations a second, this is what each size allows.

If n is up to	Aim for	Usually means
10 – 11	O(n!)	Every permutation: backtracking, brute-force ordering.
20 – 25	O(2ⁿ), O(n·2ⁿ)	Every subset: include / exclude recursion, bitmask DP.
≈ 500	O(n³)	Interval DP, Floyd–Warshall, three nested loops.
≈ 5,000	O(n²)	2-D DP over two indices (LCS, edit distance), all pairs.
10⁵ – 10⁶	O(n log n)	Sort first, a heap, binary search inside a loop. The most common interview bound.
10⁷ – 10⁸	O(n)	One pass: hash map, two pointers, sliding window, prefix sums, BFS / DFS.
beyond 10⁸	O(log n), O(1)	Binary search on the answer, math, a formula.

If n is up to

Aim for

Usually means

10 – 11

O(n!)

Every permutation: backtracking, brute-force ordering.

20 – 25

O(2ⁿ), O(n·2ⁿ)

Every subset: include / exclude recursion, bitmask DP.

≈ 500

O(n³)

Interval DP, Floyd–Warshall, three nested loops.

≈ 5,000

O(n²)

2-D DP over two indices (LCS, edit distance), all pairs.

10⁵ – 10⁶

O(n log n)

Sort first, a heap, binary search inside a loop. The most common interview bound.

10⁷ – 10⁸

O(n)

One pass: hash map, two pointers, sliding window, prefix sums, BFS / DFS.

beyond 10⁸

O(log n), O(1)

Binary search on the answer, math, a formula.

Where each class comes from

Recognise the code shape and you know the bound before you count anything.

Rules for stating it in an interview

Drop constants and lower-order terms. 3n² + 10n + 7 is O(n²). Two passes over the array is still O(n).
Sequential steps add, nested steps multiply. A loop then another loop is O(a + b); a loop inside a loop is O(a · b).
Different inputs get different letters. Comparing two strings is O(m · n), not O(n²); a graph is O(V + E). Collapsing them to n is the most common way to state a wrong bound.
Halving gives a log. Whenever each step cuts the remaining work in half — binary search, a balanced tree, a heap — the step count is log n. The base never matters: log₂ n and log₁₀ n differ by a constant.
Recursion is branches^depth. Naive Fibonacci makes 2 calls, n deep: O(2ⁿ). Memoise it and each state is computed once: O(states × work per state) = O(n).
Divide and conquer: split in half, do linear work to merge — O(n log n) (merge sort). Split in half and keep one side — O(log n) (binary search).
Amortised counts the whole run. A dynamic array's occasional resize, or a monotonic stack where each item is pushed and popped once, is O(1) per operation over the run — say "amortised" out loud.
Space includes the recursion stack. A DFS on a skewed tree is O(n) space even with no data structure in sight; on a balanced one it is O(log n).
Name the line that sets it. "The sort is O(n log n) and everything after it is linear, so the total is O(n log n)" is the sentence an interviewer is listening for.

The classic Big-O chart (reference image)

Big-O complexity chart: operations against elements, from O(1) and O(log n) in the excellent band to O(2^n) and O(n!) in the horrible band

Practise it: the complexity quiz shows a snippet and asks for its time and space · the cheat sheets state the bound of every template.