Big-O in Practice
Reading the time complexity of real code: loops, nested loops, halving, and the common complexity classes from O(1) to O(2^n).
On this page
You've met Big-O before as a concept. In interviews it's a tool you use out loud: for every solution you propose, you state its time and space complexity, and you use it to compare approaches. This lesson is about reading complexity off real code quickly and correctly.
Big-O is about growth, not seconds
Big-O describes how the work grows as the input grows, ignoring constants and lower-order terms.
An algorithm that does 3n + 100 steps is O(n); one that does n^2 / 2 steps is O(n^2). We drop
the constants because for large inputs, the shape of the growth dominates everything else.
- O(1)≈ 1
- O(log n)≈ 4
- O(n)≈ 16
- O(n log n)≈ 64
- O(n²)≈ 256
At n = 16, an O(n²) algorithm does about 256 operations while O(log n) does only 4. That gap is why complexity matters at scale.
Reading it off the code
A few reliable rules cover most interview code:
- A simple loop over n items → O(n).
- A loop inside a loop, both over n → O(n^2). Three nested → O(n^3).
- Halving the input each step (binary search, balanced-tree descent) → O(log n).
- A loop that does a log-n operation each iteration (n inserts into a heap) → O(n log n).
- Two separate loops → O(n) + O(n) = O(n), not O(n^2). Sequential adds; nesting multiplies.
// O(n): one pass
for (int x : a) sum += x;
// O(n^2): nested passes over the same input
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
grid[i][j] = i * j;
// O(log n): the search space halves every step
int lo = 0, hi = n - 1;
while (lo <= hi) { int mid = (lo + hi) >>> 1; /* … */ }
// O(n log n): n iterations, each doing an O(log n) heap insert
for (int x : a) minHeap.offer(x);Watch the hidden loops
Complexity traps hide inside innocent-looking calls. list.contains(x) on an ArrayList is
O(n), so calling it inside a loop is O(n^2). String concatenation in a loop with + is O(n^2)
because each + copies the whole string. Ask of every line: how much work does this call actually
do?
The complexity classes, best to worst
From fastest-growing-slowest to worst: O(1) (constant) → O(log n) → O(n) → O(n log n) → O(n^2) → O(2^n) → O(n!). In interviews, O(n log n) is usually the target for sorting-based solutions, O(n) for single-pass ones, and anything O(2^n) or worse (naive recursion over subsets/permutations) is a red flag to optimize - often with memoization.
Two recipes both make dinner tonight, so timing them once tells you little. The real question is: what happens when you cook for 10 guests, then 100, then 1000? One recipe's effort grows in step with the guests (O(n)); another needs every guest to greet every other guest (O(n^2)) and collapses at scale. Big-O compares recipes by how they scale, which is what matters when inputs get large - not the stopwatch on one small run.
Give the time complexity of each: (a) summing an array; (b) checking every pair of elements for a duplicate with nested loops; (c) binary search on a sorted array; (d) sorting an array then doing one linear pass. Then say which of (b) or (d) you'd prefer for finding a duplicate, and why.
What is the time complexity of two separate (not nested) loops, each iterating over n elements?
Key takeaways
- Big-O measures how work grows with input size, dropping constants and lower-order terms.
- Simple loop = O(n); nested loops multiply (O(n^2)); halving the input = O(log n); n log-n operations = O(n log n).
- Sequential loops add (still O(n)); only nesting multiplies.
- Watch hidden costs: ArrayList.contains is O(n), and String + in a loop is O(n^2).
- Know the ladder O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < O(2^n), and treat exponential as a cue to optimize.