menu_bookGyanByte
Lesson 023 min read

Big-O Made Intuitive

November 05, 2026

// TL;DR

Big-O describes how an algorithm's work GROWS with input size n, ignoring constants — O(n²) means doubling n quadruples the work. The classes you need, fastest to slowest: O(1) constant, O(log n) binary search, O(n) one pass, O(n log n) good sorts, O(n²) nested loops, O(2ⁿ)/O(n!) exponential (subsets/permutations). In interviews you don't prove anything — you (1) state your solution's time AND space, and (2) use the input SIZE in the constraints to choose an approach: n ≤ 20 → exponential/backtracking is fine; n = 10⁵ → you need O(n log n) or O(n); n = 10⁹ → O(log n) or O(1). Rules of thumb: a loop = O(n), nested loops = O(n²), halving = O(log n), recursion branching into 2 = O(2ⁿ). The constraints are a hint about the intended pattern.

You need just enough complexity theory to talk about your solutions and choose an approach. No proofs, no limits — just intuition. This lesson gives you exactly that.

What Big-O means

Big-O describes how the amount of work grows as the input size n grows, ignoring constant factors and lower-order terms. O(n²) does not mean “n² operations exactly”; it means “if you double n, the work roughly quadruples.” We drop constants because for large n they don’t matter — O(2n) and O(n) are both just O(n). We care about the shape of the growth, because that’s what decides whether your solution is fast enough.

The classes you actually need

Big-O, how fast does work grow. A growth chart of ops versus input size n with six curves: O(1) flat, O(log n) barely rising, O(n) a straight line, O(n log n) slightly curved up, O(n squared) a steep curve, and O(2 to the n) exploding. A rough budget for about one second: O(1) and O(log n) handle any n; O(n) and O(n log n) up to about 10 to the 7 or 8; O(n squared) up to about 10 thousand; O(2 to the n) and O(n factorial) up to about 20 to 25 with n small. So n up to 20 hints at backtracking; n equals 100 thousand means you need O(n log n) or better. Read the constraints, they tell you the intended complexity: Big-O describes how work grows ignoring constants; in interviews state your solution's time and space, and use the input size to pick an approach.

From fastest to slowest, with a real example of each:

  • O(1) — constant. Same work regardless of n. A hash-map lookup, array index, arithmetic.
  • O(log n) — logarithmic. Halving each step. Binary search. Growing n barely adds work (a billion items is only ~30 steps).
  • O(n) — linear. One pass over the input. A single loop, a sliding window, a BFS/DFS of a list.
  • O(n log n) — linearithmic. The speed of good comparison sorts (and anything that sorts then scans). Usually the target for “efficient” solutions.
  • O(n²) — quadratic. Nested loops over the input. Fine for small n, too slow for large.
  • O(2ⁿ) / O(n!) — exponential / factorial. Trying all subsets / permutations (backtracking). Only works for tiny n.

Estimating your code — simple rules

  • A single loop over n items → O(n).
  • Two nested loops over n → O(n²); three nested → O(n³).
  • Each step halves the space → O(log n).
  • Sort the data → O(n log n).
  • Recursion that branches into 2 calls, depth n → O(2ⁿ); permutations → O(n!).
  • Space counts too: an extra hash map or array is O(n) space; recursion uses O(depth) stack space. Always state both time and space.

Don’t forget to simplify: O(n + n²) is just O(n²); O(2n + 5) is O(n).

Read the constraints — they tell you the answer

This is the practical superpower. The problem’s input size tells you the intended complexity, and therefore often the pattern:

n ≤ 20          → O(2ⁿ) or O(n!) is fine  → think backtracking / bitmask
n ≤ 1,000–5,000 → O(n²) is fine           → nested loops, 2-D DP
n ≤ 100,000     → need O(n log n) or O(n)  → sorting, sliding window, heap
n ≤ 10,000,000  → need O(n) or O(n log n)
n up to 10⁹     → need O(log n) or O(1)    → binary search, maths

So when you see n = 10⁵, you know a brute-force O(n²) will time out, and you should look for an O(n log n) or O(n) pattern. When you see n ≤ 20, exponential search is expected. Always read the constraints first — they are the interviewer quietly telling you what they want.

Pitfalls

  • Forgetting space complexity. Interviewers often ask “can you do it in O(1) space?” Know your extra memory, not just time.
  • Ignoring the constraints. Writing O(n²) when n = 10⁵ wastes everyone’s time. Let the input size guide the approach.
  • Over-counting constants. O(3n) is O(n); don’t say “O(3n)“. But do mention a hidden factor like string length if it’s significant.

Recap

Big-O is the growth rate of work as n grows, constants ignored. Know the ladder — O(1), O(log n), O(n), O(n log n), O(n²), O(2ⁿ) — and how to read it off your code (loop = O(n), nested = O(n²), halving = O(log n)). State time and space for every solution. And read the constraints: the input size tells you the required complexity and hints at the pattern. That’s all the complexity theory an interview needs.

Next: Lesson 3 — Two Pointers, the first and most fundamental pattern.

coding-interviewbig-ocomplexityalgorithms
arrow_back PreviousHow Coding Interviews Really WorkNext arrow_forwardTwo Pointers