Big O Cheat Sheet — Time and Space Complexity
Big O notation describes how an algorithm's time or space requirements scale as the input size grows. It is the universal language for comparing algorithm efficiency and a core topic in coding interviews. This guide covers all major complexity classes, data structure operation complexities, and common sorting algorithm complexities — with practical examples for each.
Big O Complexity Classes
| Notation | Name | Description | Examples | Rating |
|---|---|---|---|---|
| O(1) | Constant | Same time regardless of input size | Array access by index, hash table lookup (average), push/pop from stack | Best |
| O(log n) | Logarithmic | Time grows very slowly -- each step halves the problem | Binary search, balanced BST lookup, heap insert/delete | Excellent |
| O(n) | Linear | Time grows proportionally with input size | Linear search, traversing a linked list, single-pass scan | Good |
| O(n log n) | Linearithmic | Slightly worse than linear -- typical optimal sorting | Merge sort, heap sort, quicksort (average), most efficient comparison sorts | Acceptable |
| O(n^2) | Quadratic | Time grows with the square of input -- nested loops | Bubble sort, insertion sort, selection sort, comparing all pairs | Poor for large n |
| O(2^n) | Exponential | Time doubles with each additional input element | Naive recursive Fibonacci, brute-force subset generation, travelling salesman (brute force) | Avoid for n > 20 |
| O(n!) | Factorial | Time grows as factorial of input -- all permutations | Brute-force travelling salesman (all routes), brute-force scheduling | Avoid for n > 10 |
Data Structure Time Complexities
| Data structure | Access | Search | Insert (end) | Delete | Space |
|---|---|---|---|---|---|
| Array | O(1) | O(n) | O(1) amortised | O(n) | O(n) |
| Singly linked list | O(n) | O(n) | O(1) with tail ptr | O(n) | O(n) |
| Hash table | N/A | O(1) avg / O(n) worst | O(1) avg | O(1) avg | O(n) |
| Binary search tree (balanced) | O(log n) | O(log n) | O(log n) | O(log n) | O(n) |
| Heap (binary) | Min/max: O(1) | O(n) | O(log n) | O(log n) | O(n) |
| Stack / Queue | O(n) | O(n) | O(1) | O(1) | O(n) |
What Big O Actually Means
Big O describes the worst-case upper bound of an algorithm's growth rate. Key properties:
- Drop constants: O(2n) = O(n). Big O cares about growth rate, not exact counts. A for-loop with 3 operations per iteration is still O(n), not O(3n).
- Drop non-dominant terms: O(n^2 + n) = O(n^2). For large n, the n^2 term dominates completely — the n term is irrelevant.
- Worst case by default: O(n) for linear search means it might check all n elements. In the best case it finds the item at index 0 in O(1) — but the Big O is still written as O(n).
- Input size matters: For n=10, O(n^2)=100 vs O(n)=10. For n=1,000,000, O(n^2)=10^12, O(n log n)≈20,000,000, O(n)=1,000,000. The difference becomes enormous.
Sorting Algorithm Complexities
The practical hierarchy for sorting:
- Merge sort: O(n log n) best/average/worst. Stable. O(n) space. Predictable performance — consistent choice for production.
- Quicksort: O(n log n) average, O(n^2) worst case (poor pivot selection — rare with randomised pivot). O(log n) space. Fast in practice due to cache efficiency. Used in most standard library sorts.
- Heapsort: O(n log n) guaranteed. O(1) space. Not stable. Rarely used in practice — worse cache performance than quicksort despite same complexity.
- Timsort (Python, Java, modern langs): O(n log n) worst case; O(n) on nearly-sorted data. Hybrid of merge sort and insertion sort. Stable.
- Counting sort / Radix sort: O(n) — but only for integer keys within a known range. Not a comparison sort — bypasses the O(n log n) lower bound for comparison sorts.
- Bubble / Insertion / Selection sort: O(n^2). Only use for very small n (< ~20 elements) or nearly-sorted data (insertion sort is O(n) for nearly-sorted input).
Space Complexity
Space complexity measures how much additional memory an algorithm uses relative to input size. Types:
- O(1) space: Constant — algorithm uses a fixed amount of extra memory regardless of input. Ideal. Example: in-place sort (bubble sort, heapsort).
- O(log n) space: Logarithmic — typical of recursive algorithms where stack depth is O(log n). Example: recursive binary search call stack.
- O(n) space: Linear — memory scales with input. Example: merge sort's auxiliary array; recursion with depth n.
Space and time complexity often trade off. Hash tables use O(n) space to achieve O(1) lookup (instead of O(n) linear search with O(1) space). Dynamic programming uses O(n) or O(n^2) space to achieve polynomial-time solutions to problems that would otherwise be exponential.
Amortised Analysis
Some operations are occasionally expensive but cheap on average — amortised analysis averages the cost over many operations. The key example:
Dynamic array append: Appending to an array is O(1) most of the time. But when the array is full, it must reallocate and copy all elements — O(n). If the array doubles in size on each resize, resizes happen exponentially less often. The amortised cost per append is O(1) — the O(n) resizes are infrequent enough that when spread across all operations, each operation averages O(1).
This is why Python's list.append(), Java's ArrayList.add(), and JavaScript's Array.push() are all described as O(1) amortised, despite occasionally triggering O(n) resizes.
Practical Big O: When Does It Matter?
Big O matters most when:
- Input can be large: n=100 is fine for O(n^2); n=10,000,000 is not.
- The operation is repeated in a loop: An O(n) operation inside an O(n) loop = O(n^2) overall.
- In coding interviews: Interviewers assess whether you know when a naive O(n^2) solution can be improved to O(n log n) or O(n).
Big O does not always determine which algorithm is faster in practice — constant factors matter for small n. A well-optimised O(n^2) algorithm can outperform a poorly-implemented O(n log n) one for small inputs. Profile first, then optimise.
Common Questions
What is the difference between O(log n) and O(n log n)?
O(log n) — logarithmic — is much faster than O(n log n) — linearithmic. For n = 1,000,000: O(log n) ≈ 20 operations; O(n log n) ≈ 20,000,000 operations. The difference is a factor of n. O(log n) is typical of binary search (halve the search space each step). O(n log n) is typical of efficient sorting (must examine all n elements, with each element taking O(log n) work on average).
What is the best time complexity for sorting?
For comparison-based sorting (algorithms that determine order by comparing elements), O(n log n) is the theoretical minimum — it can be proven that you cannot sort faster than this in the worst case with comparisons alone. Non-comparison sorts (counting sort, radix sort, bucket sort) can achieve O(n) for specific input types (integer keys within a bounded range), bypassing this lower bound.
What does O(1) space mean for an in-place algorithm?
O(1) (constant) space means the algorithm uses a fixed amount of extra memory that does not grow with input size — typically a handful of variables for swapping, counting, or tracking state. The input array itself is not counted in space complexity (it was already allocated). Heapsort and bubble sort are O(1) space. Merge sort is O(n) space because it needs an auxiliary array the same size as the input for the merge step. Recursion depth also counts as space — a recursive algorithm with depth n uses O(n) stack space even if it has no other allocation.
Visualise Algorithm Complexity
Use the Big O visualiser to compare how different complexities scale with input size — see the growth curves side by side.
Open Big O Visualiser