Big O Complexity Cheat Sheet
Interactive algorithm complexity reference covering 28 algorithms across sorting, searching, data structures, and graph algorithms. Filter by category, search by name, and compare best, average, worst, and space complexities. No signup, runs entirely in your browser.
⏱ 10 min read · Complete guide below
| Algorithm | Best | Average | Worst | Space | Notes |
|---|---|---|---|---|---|
| Bubble Sort | O(n) | O(n²) | O(n²) | O(1) | Stable; rarely used in practice |
| Selection Sort | O(n²) | O(n²) | O(n²) | O(1) | Not stable; minimal swaps |
| Insertion Sort | O(n) | O(n²) | O(n²) | O(1) | Stable; fast for small / nearly-sorted arrays |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Stable; consistent performance |
| Quick Sort | O(n log n) | O(n log n) | O(n²) | O(log n) | Not stable; worst case with bad pivots |
| Heap Sort | O(n log n) | O(n log n) | O(n log n) | O(1) | Not stable; in-place |
| Tim Sort | O(n) | O(n log n) | O(n log n) | O(n) | Stable; used in Python/Java |
| Counting Sort | O(n+k) | O(n+k) | O(n+k) | O(k) | Stable; k = range of input values |
| Radix Sort | O(nk) | O(nk) | O(nk) | O(n+k) | Stable; k = number of digits |
| Linear Search | O(1) | O(n) | O(n) | O(1) | Works on unsorted arrays |
| Binary Search | O(1) | O(log n) | O(log n) | O(1) | Array must be sorted |
| Jump Search | O(1) | O(√n) | O(√n) | O(1) | Sorted arrays; block size √n |
| Interpolation Search | O(1) | O(log log n) | O(n) | O(1) | Uniform distribution assumed |
| Exponential Search | O(1) | O(log n) | O(log n) | O(1) | Unbounded / infinite arrays |
| Array (access) | O(1) | O(1) | O(1) | O(n) | Random access by index |
| Array (search) | O(1) | O(n) | O(n) | O(n) | Unsorted; O(log n) if sorted |
| Array (insert) | O(1) | O(n) | O(n) | O(n) | O(1) at end; O(n) at front/middle |
| Linked List | O(1) | O(n) | O(n) | O(n) | O(1) insert/delete at head |
| Hash Table | O(1) | O(1) | O(n) | O(n) | Worst case with hash collisions |
| BST (balanced) | O(log n) | O(log n) | O(log n) | O(n) | AVL, Red-Black; guaranteed log n |
| BST (unbalanced) | O(log n) | O(log n) | O(n) | O(n) | Degrades to O(n) if skewed |
| Stack / Queue | O(1) | O(1) | O(1) | O(n) | Push, pop, enqueue, dequeue all O(1) |
| Heap (min/max) | O(1) | O(log n) | O(log n) | O(n) | O(1) peek; O(log n) insert/extract |
| BFS | O(V+E) | O(V+E) | O(V+E) | O(V) | V = vertices, E = edges |
| DFS | O(V+E) | O(V+E) | O(V+E) | O(V) | Recursive stack depth = O(V) |
| Dijkstra's | O(E log V) | O(E log V) | O(E log V) | O(V) | Min-heap; non-negative weights |
| Bellman-Ford | O(VE) | O(VE) | O(VE) | O(V) | Handles negative weights |
| Floyd-Warshall | O(V³) | O(V³) | O(V³) | O(V²) | All-pairs shortest path |
| Kruskal's MST | O(E log E) | O(E log E) | O(E log E) | O(V) | Minimum spanning tree; sorts edges |
How to Use the Big O Cheat Sheet
- 1Filter by category — sorting, searching, data structures, or graph algorithms.
- 2Search by algorithm name to jump straight to one you are studying.
- 3Compare the best, average, worst, and space complexities side by side.
- 4Lead with the worst case when choosing between algorithms for real workloads.
Worked Example: Why O(n log n) Beats O(n²) at Scale
Compare two sorts on an array of one million elements (n = 10⁶). Bubble Sort is O(n²), so it does roughly (10⁶)² = 10¹² operations — a trillion. Merge Sort is O(n log n): log₂(10⁶) ≈ 20, so it does about 10⁶ × 20 = 2 × 10⁷ operations— twenty million. That is a 50,000× difference. At a billion operations per second, the merge sort finishes in a fraction of a second while the bubble sort grinds for around 17 minutes.
But the cheat sheet also shows why asymptotics aren't the whole story. For a tiny array of 20 items, Insertion Sort's O(n²) is only ~400 operations with almost no overhead, so it beats Merge Sort's recursion and O(n) extra memory in practice — which is exactly why Timsort (the sort in Python and Java) runs insertion sort on small runs and merge sort on large ones. Read complexity to predict behaviour at scale, then check the space column and the constant factors before committing.
What Big O Notation Measures
Big O notation describes how an algorithm's resource use — usually time, sometimes memory — grows as the input size n increases. Crucially, it is about the rate of growth, not the exact running time: it deliberately ignores constant factors and hardware speed to capture how an algorithm scales. That is why an O(n) algorithm is considered better than an O(n²) one for large inputs even if the O(n²) version happens to be faster on tiny inputs. The common classes, from best to worst, run O(1)(constant), O(log n) (logarithmic), O(n) (linear), O(n log n), O(n²) (quadratic), and O(2ⁿ) (exponential). Learning to recognise which class a piece of code falls into is one of the most useful skills in practical programming.
Best, Average, and Worst Case
Many algorithms do not have a single complexity — their performance depends on the input, which is why the cheat sheet lists best, average, and worst cases separately. The best case is the most favourable input (a nearly-sorted array for insertion sort, for example), the average case is expected performance on typical data, and the worst case is the slowest possible scenario. For most real decisions the worst case matters most, because it is the guarantee you can rely on: an algorithm that is O(n log n) in the worst case is safer for a critical system than one that is O(n log n) on average but degrades to O(n²) on certain inputs. Reading all three columns together, rather than just one, gives you the full performance picture.
Why Asymptotics Aren't the Whole Story
Big O predicts behaviour at scale, but it deliberately hides two things that matter in practice: constant factors and memory use. For small inputs, an algorithm with worse Big O can easily win because it has less overhead — which is exactly why real-world sorts like Timsort (used in Python and Java) run simple insertion sort on small runs and switch to merge sort only for larger ones. The space column also deserves attention: two algorithms with identical time complexity can differ sharply in memory, and the faster one in theory may lose in practice due to cache misses. The right workflow is to use Big O to predict how something scales, then check the constants, the memory cost, and the actual input sizes you expect before choosing. This cheat sheet puts all of those factors in one place so you can weigh them together.
How to Use Big O Notation
Start with worst case
When comparing algorithms, always check worst-case complexity first. An algorithm that is O(n log n) worst case is safer than one that is O(n log n) average but O(n²) worst case.
Space vs time trade-off
Faster algorithms often use more memory. Merge Sort achieves O(n log n) time but requires O(n) extra space; Heap Sort achieves the same time with O(1) space but is slower in practice due to cache misses.
Constants matter for small n
For small input sizes (n < 50), insertion sort often outperforms Quick Sort despite worse asymptotic complexity because overhead and constants dominate. That is why Timsort uses insertion sort for small runs.
Hash table caveats
Hash map lookups are O(1) average but O(n) worst case due to hash collisions. Most production hash maps handle this with open addressing or chaining, keeping average performance excellent.
A Tour of the Common Complexity Classes
The complexity classes are easier to remember when you attach a concrete example to each. Starting from the fastest: O(1) constant time means the work does not grow with input at all — looking up an array element by index, or reading a value from a hash map, takes the same time whether the collection holds ten items or ten million. O(log n) logarithmic time grows extremely slowly, roughly adding one step each time the input doubles; binary search is the classic example, halving the search space with every comparison. Doubling a billion-item sorted array adds just one extra step.
O(n) linear time scales in direct proportion to the input — a single loop over a list, such as finding the maximum value, does n units of work. O(n log n) is the sweet spot of efficient sorting: it is only slightly worse than linear and is the best any comparison-based sort can achieve. O(n²) quadratic time appears whenever you nest one loop inside another over the same data — comparing every pair of items, as naive sorts and some brute-force checks do — and it becomes painful surprisingly quickly. Beyond that lie O(2ⁿ) exponential and O(n!) factorial time, seen in brute-force solutions to problems like the travelling salesman or generating all permutations; these are usable only for tiny inputs, because their growth is explosive.
How to Work Out the Complexity of Your Own Code
You do not need a formula to estimate an algorithm's Big O — a few simple rules cover most everyday code. First, count the loops over your input. A single loop from 1 to n is O(n); two loops nested over the same n is O(n²); three nested is O(n³). A loop that halves the problem each iteration — dividing by two, like binary search — contributes an O(log n) factor. Second, drop the constants and non-dominant terms. Big O cares only about the fastest-growing part: an algorithm doing n² + n + 100 operations is simply O(n²), because for large n the n² term dwarfs everything else, and the constant 100 is irrelevant.
Third, add sequential steps but multiply nested ones. Two separate loops that each run n times is O(n) + O(n) = O(n); a loop of n containing a loop of n is O(n) × O(n) = O(n²). Fourth, for recursion, think about how many times the function calls itself and how the input shrinks each time: a function that makes one recursive call on half the data is O(log n), while one that makes two calls on half the data (like a naive Fibonacci) explodes toward O(2ⁿ). Applying these rules to a function — identify the loops and recursion, keep only the dominant term, drop the constants — will correctly classify the overwhelming majority of code you write, and the table above lets you sanity-check your answer against well-known algorithms.
Why This Matters in Real Engineering
Complexity analysis is not an academic exercise reserved for interviews — it is the difference between software that scales and software that collapses under load. A feature that works instantly on a developer's test data of a hundred rows can become unusably slow at a million if it hides an O(n²) loop, and no amount of faster hardware fixes a fundamentally worse growth rate; doubling the machine speed only buys a constant factor, while the algorithm's scaling keeps pulling ahead. This is why experienced engineers instinctively ask “how does this behave as the data grows?” before shipping. Use this cheat sheet as a quick reference while you build that instinct: look up the algorithm you are about to use, check its worst-case and space complexity, and confirm it can handle the input sizes you actually expect — well before those inputs arrive in production.
Frequently Asked Questions
What is Big O notation?
Big O notation describes how the runtime or memory usage of an algorithm scales with input size n. It expresses the upper bound of growth. O(1) means constant time regardless of input; O(n²) means runtime grows with the square of input size.
What is the difference between best, average, and worst case?
Best case is the fastest the algorithm can run (e.g. a sorted array for insertion sort). Average case is expected performance on typical data. Worst case is the slowest possible scenario and is the most commonly cited for safety-critical comparisons.
What does O(n log n) mean?
O(n log n) means the algorithm performs roughly n × log₂(n) operations. This is the complexity of efficient comparison-based sorting algorithms like Merge Sort and Heap Sort. For n = 1,000,000, that is about 20 million operations instead of 1 trillion for O(n²).
Which sorting algorithm is fastest in practice?
Quick Sort is often fastest in practice despite O(n²) worst case because its cache behavior is excellent and average case is O(n log n). Most standard libraries (Python, Java, etc.) use Timsort, a hybrid of Merge Sort and Insertion Sort.
What is amortized complexity?
Amortized complexity averages the cost of an operation over a sequence of operations. For example, a dynamic array push is O(1) amortized because occasional O(n) resize operations are spread across many O(1) pushes.
Is my data stored when I use this tool?
No. The cheat sheet is entirely static — no data is entered or sent anywhere. It runs fully in your browser.
Why does Big O ignore constant factors?
Big O is designed to describe how an algorithm scales as input grows, not its exact running time on a particular machine. Constant factors and hardware speed change the absolute time but not the growth rate, so ignoring them lets you compare algorithms in a way that holds regardless of the computer running them. The trade-off is that for small inputs, an algorithm with a worse Big O but smaller constants can be faster — which is why constants still matter in practice even though Big O leaves them out.
Which complexity should I look at when choosing an algorithm?
Usually the worst case, because it is the performance guarantee you can rely on no matter what input arrives. An algorithm that is O(n log n) in the worst case is safer for critical systems than one that averages O(n log n) but can degrade to O(n²) on certain inputs. That said, if you know your data is typically random or well-behaved, the average case may be a fairer guide. Reading best, average, and worst together gives the complete picture.
What is the difference between time and space complexity?
Time complexity describes how the number of operations grows with input size, while space complexity describes how the extra memory an algorithm needs grows with input size. They are often in tension: a faster algorithm may use more memory. Merge Sort, for instance, runs in O(n log n) time but needs O(n) extra space, whereas Heap Sort matches the time with only O(1) extra space but is slower in practice due to poorer cache behaviour. The cheat sheet lists both so you can weigh the trade-off.
Why is a hash table lookup O(1) if it can be O(n)?
Hash table lookups are O(1) on average because a good hash function distributes keys evenly, so most lookups touch only one or a few slots regardless of table size. The O(n) worst case happens when many keys collide into the same bucket, degrading the structure toward a linear scan. In practice, well-designed hash maps use techniques like chaining or open addressing plus resizing to keep collisions rare, so the average O(1) behaviour holds for real workloads.
What does "amortized" complexity mean?
Amortized complexity is the average cost of an operation spread over a long sequence of operations, rather than the cost of any single one. The classic example is appending to a dynamic array: most pushes are O(1), but occasionally the array is full and must be resized in O(n). Because those expensive resizes are rare and their cost is spread across many cheap pushes, the amortized cost of a push is O(1). It is a fairer measure than worst case when occasional expensive operations are guaranteed to be infrequent.