Big-O: how engineers talk about speed
Two correct solutions to the same problem can differ so much in speed that one finishes in a millisecond and the other outlives the interview. Engineers need a way to compare algorithms before running them, one that does not depend on whose laptop is faster — and interviewers will ask you for it by name in nearly every technical interview. That language is big-O notation, and this unit's patterns only make sense with it, so we learn it first.
The time complexity of a piece of code is how the number of basic steps it performs grows as its input size grows. Input size is written n — the length of the string, the number of elements in the array.
Big-O notation summarizes that growth by keeping only the dominant trend and dropping constant factors: a loop that does 3n + 5 steps is written O(n), read "order n", because for large n the tripling and the +5 stop mattering compared to the shape of the curve. We say such code is linear: double the input, double the work.
The classes you will actually meet
| Big-O | Name | Typical shape | At n = 1,000,000 |
|---|---|---|---|
| O(1) | constant | one HashMap get/put | 1 step |
| O(log n) | logarithmic | halving each round (binary search) | ~20 steps |
| O(n) | linear | one pass over the data | 10⁶ steps |
| O(n log n) | linearithmic | good sorting (Arrays.sort) | ~2×10⁷ steps |
| O(n²) | quadratic | a loop nested inside a loop | 10¹² steps — minutes, not milliseconds |
The table is why complexity matters: at a million elements, the gap between O(n) and O(n²) is the gap between "instant" and "go get lunch". When one algorithm's big-O beats another's, we say it is asymptotically faster — faster in the trend as n grows, whatever the constant factors do on small inputs.
Two reading rules cover most code you will analyze:
- Steps in sequence add, and the biggest term wins: a pass then another pass is O(n) + O(n) = O(n).
- Nesting multiplies: a full inner loop per outer pass is n × n = O(n²).
One refinement you will meet immediately: an operation is O(1) amortized when its cost averages out to constant over many calls, even though a rare individual call is expensive. ArrayList.add is the classic case — occasionally it must copy everything into a bigger internal array (an O(n) moment), but that happens so rarely that n adds still cost O(n) total, i.e. O(1) each on average.
Code exercise · java
Run this. Both loops process n = 1000, but the nested version does a full inner sweep for every outer pass: one thousand steps versus one million. Change n to 2000 and predict both numbers before rerunning — the linear count doubles, the quadratic count quadruples.
Quiz
A method loops over an array once, and inside that loop calls stock.containsKey(...) on a HashMap (an O(1) operation). What is the method's time complexity?
Quiz
Checking every pair in an n-element array with two nested loops is O(n²). Your n is 10,000. Roughly how many steps is that, and is it fine?