Big O Cheat Sheet
A filterable reference for data structure operations and sorting algorithm complexity — best, average, worst case, and space, at a glance.
Data structure operations
Time complexity for common operations, plus space complexity. Green is fast, amber is linear, red is quadratic or worse.
| Structure | Access | Search | Insert | Delete | Space |
|---|---|---|---|---|---|
Array | O(1) | O(n) | O(n) | O(n) | O(n) |
Stack | O(n) | O(n) | O(1) | O(1) | O(n) |
Queue | O(n) | O(n) | O(1) | O(1) | O(n) |
Singly Linked List insert/delete O(1) only at a known node | O(n) | O(n) | O(1) | O(1) | O(n) |
Doubly Linked List | O(n) | O(n) | O(1) | O(1) | O(n) |
Hash Table average case — degrades to O(n) worst case on collisions | N/A | O(1) | O(1) | O(1) | O(n) |
Binary Search Tree average case — degrades to O(n) worst case if unbalanced | O(log n) | O(log n) | O(log n) | O(log n) | O(n) |
AVL / Red-Black Tree self-balancing — O(log n) is guaranteed, not just average | O(log n) | O(log n) | O(log n) | O(log n) | O(n) |
Binary Heap access is O(1) only for the min/max element | O(1) | O(n) | O(log n) | O(log n) | O(n) |
Trie k = key length, independent of how many keys are stored | O(k) | O(k) | O(k) | O(k) | O(nk) |
Graph (adjacency list) V = vertices, E = edges | N/A | O(V+E) | O(1) | O(V+E) | O(V+E) |
Sorting algorithm complexity
Best, average, and worst-case time complexity, space complexity, and whether equal elements keep their original order (stable).
| Algorithm | Best | Average | Worst | Space | Stable |
|---|---|---|---|---|---|
| Bubble Sort | O(n) | O(n²) | O(n²) | O(1) | Yes |
| Selection Sort | O(n²) | O(n²) | O(n²) | O(1) | No |
| Insertion Sort | O(n) | O(n²) | O(n²) | O(1) | Yes |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes |
| Quick Sort | O(n log n) | O(n log n) | O(n²) | 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(n+k) | Yes |
| Radix Sort | O(nk) | O(nk) | O(nk) | O(n+k) | Yes |
| Bucket Sort | O(n+k) | O(n+k) | O(n²) | O(n) | Yes |
Big O Cheat Sheet guide
Developer Tool
Interview prep and code review both come back to the same question over and over: what's the time complexity of this? A visualizer is the right tool when you want to build intuition for how a curve grows — this page is the right tool when you already know that and just need the answer fast. It's a reference, not a lesson: filter by name, read the color, move on. Green means O(1) or O(log n) — fast regardless of input size. Amber means linear or log-linear — fine for most inputs, worth a second look at scale. Red means O(n²) or worse — the kind of complexity that's invisible on a 10-item test array and very visible in production.
How to read the table
Data structure operations are split into access, search, insert, and delete because they rarely share a complexity class — a dynamic array gives O(1) access but O(n) insert at the front, while a hash table flips that trade-off entirely for O(1) average access by key. Most complexities listed here are average case; where the worst case is meaningfully different (hash tables under collision, an unbalanced binary search tree), the note under the name calls it out explicitly rather than hiding it.
The sorting table separates best, average, and worst case because several classic algorithms behave very differently depending on the input. Quick sort is O(n log n) on typical data and a common interview favorite, but degrades to O(n²) on already-sorted input with a naive pivot — worth knowing before you claim it in an interview. Stability matters when you are sorting objects by one key but need ties to keep their original relative order, e.g. sorting an already-name-sorted list by department.
Cheat sheet vs. visualizer
This page is deliberately just a table: fast to scan, easy to filter, nothing to wait for. If you want to actually see why O(n log n) pulls away from O(n²) as input grows, or compare two complexity classes on the same chart, the Time Complexity Visualizer does that with interactive, adjustable curves. Use the cheat sheet to recall a fact in ten seconds; use the visualizer to build the intuition behind it.
Both pull from the same underlying complexity classes, so terminology stays consistent whichever one you land on first — useful if you are bouncing between the two while prepping for a system design or data structures interview.
Related tools
Explore these related tools to complete your workflow faster.