Big-O cheat sheet
The time complexity of common data structures and sorting algorithms on one page. Handy for exams, assignments and coding interviews.
Growth rates, from fastest to slowest
| Big-O | Name | Typical example | For large n |
|---|---|---|---|
| O(1) | Constant | Array access by index, hash table lookup | Excellent |
| O(log n) | Logarithmic | Binary search, balanced tree lookup | Excellent |
| O(n) | Linear | Scanning a list, linear search | Good |
| O(n log n) | Linearithmic | Merge sort, heap sort | Fair |
| O(n^2) | Quadratic | Bubble sort, nested loops over the data | Poor |
| O(2^n) | Exponential | Trying every subset, naive recursive Fibonacci | Very poor |
| O(n!) | Factorial | Trying every ordering, brute-force travelling salesman | Very poor |
Data structure operations
| Structure | Access | Search | Insert | Delete |
|---|---|---|---|---|
| Array | O(1) | O(n) | O(n) | O(n) |
| Singly linked list | O(n) | O(n) | O(1) at the head | O(n), or O(1) if you hold the node |
| Stack | O(n) | O(n) | O(1) push | O(1) pop |
| Queue | O(n) | O(n) | O(1) enqueue | O(1) dequeue |
| Hash table (average) | n/a | O(1) | O(1) | O(1) |
| Binary search tree (balanced) | O(log n) | O(log n) | O(log n) | O(log n) |
| Binary search tree (worst case) | O(n) | O(n) | O(n) | O(n) |
| Binary heap | O(n) | O(n) | O(log n) | O(log n) extract min or max |
For stacks and queues the useful operations are push and pop (or enqueue and dequeue), which take constant time. A hash table has no ordered access, and its worst case is O(n) if many keys collide.
Sorting algorithms
| Algorithm | Best | Average | Worst | Extra space | Stable |
|---|---|---|---|---|---|
| Bubble sort | O(n) | O(n^2) | O(n^2) | O(1) | Yes |
| Selection sort | O(n^2) | O(n^2) | O(n^2) | O(1) | No |
| Insertion sort | O(n) | O(n^2) | O(n^2) | O(1) | Yes |
| Merge sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes |
| Quicksort | O(n log n) | O(n log n) | O(n^2) | O(log n) | No |
| Heap sort | O(n log n) | O(n log n) | O(n log n) | O(1) | No |
| Counting sort | O(n + k) | O(n + k) | O(n + k) | O(k) | Yes |
Stable means equal items keep their original order. In the counting sort row, k is the range of the values.
How to find the Big-O of your own code
- Count the loops. One loop over n items is O(n). A loop inside a loop is O(n^2).
- Halving gives log n. If each step cuts the problem in half, as in binary search, it is O(log n).
- Add steps that run one after another, then keep only the biggest term. O(n) + O(n^2) becomes O(n^2).
- Drop constants. 3n and 100n are both just O(n).
Frequently asked questions
What does Big-O notation mean?
Big-O describes how the running time or memory of an algorithm grows as the input size n gets larger. It ignores small details and focuses on the growth rate.
Which is faster, O(n log n) or O(n^2)?
O(n log n) grows much more slowly, so it is faster for large inputs. Sorting 1,000,000 items takes about 20 million steps with n log n, but about a trillion with n^2.
What is the difference between best, average and worst case?
They describe how the same algorithm behaves on lucky, typical and unlucky inputs. Exams usually ask for the worst case unless they say otherwise.
Test yourself with the data structures MCQs. More free tools: truth table generator · number base converter