Big O Cheat Sheet (with Run-Time Estimator)
Big O time and space complexity of arrays, hash tables, trees, heaps, sorting and graph algorithms, plus a growth table and a run-time estimate for your n.
Big O ignores constant factors: an O(n log n) algorithm with a large constant can be slower than an O(n²) one for small n. The estimate assumes one simple operation per counted step.
| Complexity | Operations | Time |
|---|---|---|
| O(1) | 1 | < 1 µs |
| O(log n) | 16.61 | < 1 µs |
| O(√n) | 316 | 3.2 µs |
| O(n) | 100,000 | 1 ms |
| O(n log n) | 1,660,964 | 16.6 ms |
| O(n²) | 10,000,000,000 | 100 s |
| O(n³) | 1.00 × 10^15 | 115.7 days |
| O(2ⁿ) | 9.99 × 10^30,102 | 3.17 × 10^30,087 years |
| O(n!) | 2.82 × 10^456,573 | 8.95 × 10^456,557 years |
| Structure | Access | Search | Insert | Delete | Space | Note |
|---|---|---|---|---|---|---|
| Array (static) | O(1) | O(n) | O(n) | O(n) | O(n) | Insert/delete shift the elements after the position. |
| Dynamic array (vector, ArrayList, list) | O(1) | O(n) | O(1) amortized at the end · O(n) elsewhere | O(1) at the end · O(n) elsewhere | O(n) | A resize copies everything (O(n)) but happens rarely. |
| Singly linked list | O(n) | O(n) | O(1) at the head or after a known node | O(1) at the head · O(n) to find the node | O(n) | |
| Doubly linked list | O(n) | O(n) | O(1) at either end or a known node | O(1) at a known node | O(n) | |
| Stack / queue / deque | O(n) | O(n) | O(1) push / enqueue | O(1) pop / dequeue | O(n) | Only the ends are accessible in O(1). |
| Hash table (hash map, set) | — | O(1) average · O(n) worst | O(1) average · O(n) worst | O(1) average · O(n) worst | O(n) | Worst case when many keys collide; no ordering. |
| Binary search tree (unbalanced) | O(log n) average · O(n) worst | O(log n) average · O(n) worst | O(log n) average · O(n) worst | O(log n) average · O(n) worst | O(n) | Sorted input degrades it to a linked list. |
| AVL tree / red-black tree | O(log n) | O(log n) | O(log n) | O(log n) | O(n) | Worst case guaranteed by rebalancing (TreeMap, std::map). |
| B-tree / B+ tree | O(log n) | O(log n) | O(log n) | O(log n) | O(n) | Few, wide levels — used by databases and file systems. |
| Binary heap (priority queue) | O(1) min/max only | O(n) | O(log n) | O(log n) extract-min | O(n) | Building a heap from n items is O(n). |
| Trie (prefix tree) | — | O(m) | O(m) | O(m) | O(total key length) | m = length of the key, independent of n. |
| Skip list | O(log n) average | O(log n) average · O(n) worst | O(log n) average · O(n) worst | O(log n) average · O(n) worst | O(n) expected | |
| Disjoint set (union-find) | — | O(α(n)) find | O(α(n)) union | — | O(n) | With path compression and union by rank; α grows slower than log. |
| Algorithm | Best | Average | Worst | Extra space | Stable |
|---|---|---|---|---|---|
| Quicksort | O(n log n) | O(n log n) | O(n²) | O(log n) | No |
| Merge sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes |
| Heapsort | O(n log n) | O(n log n) | O(n log n) | O(1) | No |
| Timsort (Python, Java objects) | O(n) | O(n log n) | O(n log n) | O(n) | Yes |
| Introsort (C++ std::sort) | O(n log n) | O(n log n) | O(n log n) | O(log n) | No |
| Insertion sort | O(n) | O(n²) | O(n²) | O(1) | Yes |
| Selection sort | O(n²) | O(n²) | O(n²) | O(1) | No |
| Bubble sort (with early exit) | O(n) | O(n²) | O(n²) | O(1) | Yes |
| Shell sort | O(n log n) | depends on the gaps | O(n^(4/3)) with Sedgewick gaps | O(1) | No |
| Counting sort | O(n + k) | O(n + k) | O(n + k) | O(n + k) | Yes |
| Radix sort (LSD) | O(d·(n + b)) | O(d·(n + b)) | O(d·(n + b)) | O(n + b) | Yes |
| Bucket sort | O(n + k) | O(n + k) | O(n²) | O(n + k) | Yes, with a stable inner sort |
| Algorithm | Time | Space | Note |
|---|---|---|---|
| Linear search | O(n) | O(1) | Any list. |
| Binary search | O(log n) | O(1) | Sorted array only. |
| Breadth-first search (BFS) | O(V + E) | O(V) | Shortest paths in unweighted graphs. |
| Depth-first search (DFS) | O(V + E) | O(V) | Recursion depth up to V. |
| Topological sort | O(V + E) | O(V) | Kahn's algorithm or DFS; directed acyclic graphs. |
| Dijkstra (binary heap) | O((V + E) log V) | O(V) | Non-negative edge weights. |
| Bellman–Ford | O(V·E) | O(V) | Handles negative weights, detects negative cycles. |
| Floyd–Warshall | O(V³) | O(V²) | All pairs of shortest paths. |
| Prim (binary heap) | O(E log V) | O(V) | Minimum spanning tree. |
| Kruskal | O(E log E) | O(V) | Minimum spanning tree; sorting the edges dominates. |
| Matrix multiplication (naive) | O(n³) | O(n²) | n × n matrices. |
| Generating all subsets / permutations | O(2ⁿ) / O(n!) | O(n) | Feasible only for small n (about 25 / 11). |
| n | O(1) | O(log n) | O(√n) | O(n) | O(n log n) | O(n²) | O(n³) | O(2ⁿ) | O(n!) |
|---|---|---|---|---|---|---|---|---|---|
| 10 | 1 | 3.32 | 3.16 | 10 | 33.22 | 100 | 1,000 | 1,024 | 3,628,800 |
| 100 | 1 | 6.64 | 10 | 100 | 664 | 10,000 | 1,000,000 | 1.27 × 10^30 | 9.33 × 10^157 |
| 1,000 | 1 | 9.97 | 31.62 | 1,000 | 9,966 | 1,000,000 | 1,000,000,000 | 1.07 × 10^301 | 4.02 × 10^2,567 |
| 10,000 | 1 | 13.29 | 100 | 10,000 | 132,877 | 100,000,000 | 1,000,000,000,000 | 2.00 × 10^3,010 | 2.85 × 10^35,659 |
| 100,000 | 1 | 16.61 | 316 | 100,000 | 1,660,964 | 10,000,000,000 | 1.00 × 10^15 | 9.99 × 10^30,102 | 2.82 × 10^456,573 |
| 1,000,000 | 1 | 19.93 | 1,000 | 1,000,000 | 19,931,569 | 1,000,000,000,000 | 1.00 × 10^18 | 9.90 × 10^301,029 | 8.26 × 10^5,565,708 |
Big O notation describes how the work an algorithm does grows with the size of its input. This cheat sheet collects the time and space complexity of the common data structures (arrays, linked lists, hash tables, balanced trees, heaps, tries), sorting algorithms (with best, average and worst cases and stability) and graph algorithms. A calculator turns a complexity and your input size into an operation count and an estimated run time, which is the quickest way to tell whether an approach will finish in time.
How to use this tool
- Enter your input size n.
- Pick the complexity of your algorithm.
- Adjust the operations per second if you know your platform (about 10⁸ for compiled code).
- Read the operation count and estimated time, then compare all complexities at your n in the first table.
- Type in the filter box to narrow the reference tables, for example "stable" or "tree".
Formula
operations ≈ f(n) · time ≈ f(n) ÷ operations per second
f(n) is 1, log₂ n, √n, n, n log₂ n, n², n³, 2ⁿ or n!. Counts beyond 10¹⁵ are shown in scientific notation, computed with logarithms (n! with a Kahan-summed log sum, or the log-gamma function above n = 100,000). Real run time also depends on constant factors, memory access patterns and the language, so treat the estimate as an order of magnitude.
Example
Sorting n = 1,000,000 items with an O(n log n) algorithm takes about 1,000,000 × log₂ 1,000,000 ≈ 19.9 million operations — around 0.2 seconds at 10⁸ operations per second. An O(n²) algorithm needs 10¹² operations, about 2.8 hours, which is why quadratic sorts are only used for small inputs.
Frequently asked questions
What is the difference between average and worst case?
The worst case is the maximum work over all inputs of size n; the average case assumes typical or random input. Quicksort averages O(n log n) but can hit O(n²) on adversarial input, which is why libraries use introsort or randomized pivots.
What does amortized O(1) mean?
Most operations are O(1) and an occasional one is expensive, but spread over many operations the cost per operation is constant. Appending to a dynamic array is the classic example: a resize copies everything, but it happens rarely enough that the average stays O(1).
Which base is the logarithm?
In Big O the base does not matter, because logarithms of different bases differ by a constant factor. For the operation counts here, log base 2 is used.
What does stable mean for a sort?
A stable sort keeps equal elements in their original order, which matters when you sort by one key after another.
Sources
Last updated:
Page address with these inputs: https://kakao.mobile/tools/big-o-cheat-sheet/
Cite or embed this tool
kakaoCalc. (2026, November 8). Big O Cheat Sheet (with Run-Time Estimator). https://kakao.mobile/tools/big-o-cheat-sheet/
“Big O Cheat Sheet (with Run-Time Estimator).” kakaoCalc, 8 Nov. 2026, kakao.mobile/tools/big-o-cheat-sheet/.
Paste this code into your page. The widget runs in your visitors' browsers, shows no ads and keeps a link back to this page. Embedding terms