Big O notation — cheat sheet
General CS fundamentals, not tied to a specific course slide deck — but a near-certain interview topic regardless of the target role. Examples in Java, tied back to java-oop where relevant.
What it measures
Big O describes how an algorithm's running time (or memory use) grows as the input size grows — not the exact time in seconds, which depends on hardware. It's about the shape of the growth curve, not a stopwatch measurement.
- Usually describes the worst case unless stated otherwise (best/average case use different notation — Big Omega/Big Theta — rarely asked about at this level, but worth knowing the names exist).
- Constants and lower-order terms are dropped: an algorithm that does
2n + 100steps is stillO(n)— Big O cares about the dominant term asngets large, not the exact count. - Applies to both time complexity (steps taken) and space complexity (extra memory used, beyond the input itself).
Common complexities, smallest to largest
| Notation | Name | Example |
|---|---|---|
O(1) | constant | array index access arr[i], HashMap.get(key) |
O(log n) | logarithmic | binary search on a sorted array |
O(n) | linear | a single loop over a list, List.contains(x) |
O(n log n) | linearithmic | efficient sorting (Collections.sort, merge sort) |
O(n²) | quadratic | nested loop over the same collection (e.g. comparing every pair) |
O(2ⁿ) | exponential | naive recursive Fibonacci, generating all subsets |
O(n!) | factorial | generating all permutations |
As n grows, each tier gets dramatically worse than the one before it — the difference between O(n) and O(n²) at n = 1,000,000 is the difference between roughly a million steps and a trillion.
Reading complexity off code
- One loop over
nitems →O(n). - Two independent (sequential) loops over
nitems →O(n) + O(n)=O(n)(Big O drops the constant factor — still linear, not quadratic). - A loop nested inside another loop, both over the same
nitems →O(n²). - A loop that halves the problem each time (binary search, repeatedly dividing a range in half) →
O(log n). - A loop over
nthat itself does anO(log n)operation →O(n log n)(this is exactly why efficient sorting algorithms land here — sortnelements, and each placement/comparison step benefits from an already-partially-ordered/divided structure).
Complexity of common Java operations
Ties directly into 08-sets-and-maps.md — this is the concrete reason those data structures behave the way they do:
| Operation | Complexity | Why |
|---|---|---|
ArrayList.get(i) | O(1) | direct index into backing array |
ArrayList.add(x) (at the end) | O(1) amortized | occasional resize costs O(n), but rarely enough to average out |
ArrayList.contains(x) | O(n) | has to scan every element in the worst case |
ArrayList.add(i, x) / remove(i) (middle) | O(n) | has to shift every following element |
LinkedList.add/remove at a known node | O(1) | just relinks pointers |
LinkedList.get(i) | O(n) | has to walk the list from an end |
HashMap.get/put/containsKey | O(1) average | hashing jumps straight to the right bucket |
HashSet.contains/add | O(1) average | same hashing mechanism as HashMap |
Collections.sort / Stream.sorted() | O(n log n) | comparison-based sort |
String concatenation with + in a loop | O(n²) overall | String is immutable — each + builds an entirely new string, so doing it n times copies O(1) + O(2) + ... + O(n) characters total |
StringBuilder.append in a loop | O(n) overall | mutates a resizable internal buffer instead of allocating a new string each time |
That String concatenation row is a classic interview gotcha: it's exactly why the course material's repeated advice to prefer StringBuilder inside loops matters, not just a style preference.
Space complexity, briefly
Same idea, applied to memory instead of time: O(1) extra space (in-place, e.g. swapping two variables), O(n) extra space (e.g. copying a list into a new one, or the recursion stack of a non-tail-recursive function with depth n). Worth mentioning when an interviewer asks "can you do this with less memory?" — sometimes there's a time/space trade-off (e.g. a HashSet for O(1) lookups costs O(n) extra space you wouldn't need with a linear scan).
How to talk about this in an interview
You're rarely asked to derive Big O formally at this level — more likely you'll be asked "what's the time complexity of this loop/method," or asked to justify a data structure choice ("why a Set instead of a List here?"). Framing to reuse: "this is O(n) because it scans the list once", or "I'd reach for a HashMap here since we need O(1) lookups by key instead of scanning."