DSA Time Complexity Cheatsheet for Interviews
A printable cheatsheet of time and space complexities for arrays, hashmaps, trees, heaps, graphs, sorts, and common algorithms. Includes worst-case notes and quick rules of thumb.
What you'll learn
- ✓Memorize the time complexity of the most common data structure operations
- ✓Tell the difference between average-case and worst-case complexity
- ✓Pick the right structure for an interview problem under time pressure
- ✓Recall the costs of standard sorting and searching algorithms
- ✓Apply rules of thumb for when O(n log n) versus O(n) matter
Prerequisites
- •Familiarity with Big-O notation
This cheatsheet collects the complexity numbers you should be able to quote in an interview without thinking. Print it, tape it above your desk, and review it before every mock interview until the numbers are reflexive.
Arrays and Strings
Arrays in most languages give you indexed access in O(1) and bulk operations in O(n).
| Operation | Time |
|---|---|
| Access by index | O(1) |
| Search by value | O(n) |
| Insert at end (dynamic array, amortized) | O(1) |
| Insert at front or middle | O(n) |
| Delete at end | O(1) |
| Delete at front or middle | O(n) |
Strings behave like arrays of characters, but in many languages they are immutable, so concatenation is O(n + m) and building a string of length n by repeated concatenation is O(n^2). Use a builder.
Hash Maps and Hash Sets
Hash maps offer constant-time average lookups, which is why they are the workhorse of interview solutions.
| Operation | Average | Worst |
|---|---|---|
| Insert | O(1) | O(n) |
| Lookup | O(1) | O(n) |
| Delete | O(1) | O(n) |
| Iterate | O(n) | O(n) |
The worst case appears when many keys hash to the same bucket. With good hash functions and load-factor management, you almost never see it.
Linked Lists
| Operation | Singly | Doubly |
|---|---|---|
| Access by index | O(n) | O(n) |
| Insert at head | O(1) | O(1) |
| Insert at tail (with tail pointer) | O(1) | O(1) |
| Delete given node | O(n) | O(1) |
| Search by value | O(n) | O(n) |
The doubly linked list earns its keep when you already hold a reference to the node you want to delete, because you can splice it out without scanning for the predecessor.
Stacks and Queues
Both support insert and remove in O(1). Stacks use push and pop on the same end; queues use enqueue and dequeue on opposite ends. Implementations on arrays, linked lists, or dedicated deques all hit constant time for the canonical operations.
Trees
Binary search trees are the structures students learn first, but in interviews you usually want balanced variants.
| Structure | Insert | Search | Delete |
|---|---|---|---|
| Unbalanced BST (worst) | O(n) | O(n) | O(n) |
| Balanced BST (AVL, Red-Black) | O(log n) | O(log n) | O(log n) |
| Trie (by key length k) | O(k) | O(k) | O(k) |
| Segment Tree | O(log n) | O(log n) | O(log n) |
| Fenwick Tree (BIT) | O(log n) | O(log n) | O(log n) |
Trie operations depend on key length, not the number of keys stored, which is why they shine for autocomplete and prefix queries.
Heaps
Binary heaps are the standard backing store for priority queues.
| Operation | Time |
|---|---|
| Peek min or max | O(1) |
| Insert | O(log n) |
| Extract min or max | O(log n) |
| Build from array | O(n) |
| Heapify a single element down | O(log n) |
The non-obvious entry is “build heap in O(n)” — heapifying bottom-up is asymptotically cheaper than n individual inserts.
Graphs
| Algorithm | Time |
|---|---|
| BFS or DFS | O(V + E) |
| Dijkstra with binary heap | O((V + E) log V) |
| Dijkstra with Fibonacci heap | O(E + V log V) |
| Bellman-Ford | O(V * E) |
| Floyd-Warshall (all pairs) | O(V^3) |
| Topological sort | O(V + E) |
| Kruskal’s MST | O(E log E) |
| Prim’s MST with binary heap | O((V + E) log V) |
Remember that E can be as large as O(V^2) in dense graphs, which makes some of these costs less rosy than they look.
Sorting
| Algorithm | Best | Average | Worst | Stable |
|---|---|---|---|---|
| Bubble sort | O(n) | O(n^2) | O(n^2) | Yes |
| Insertion sort | O(n) | O(n^2) | O(n^2) | Yes |
| Selection sort | O(n^2) | O(n^2) | O(n^2) | No |
| Merge sort | O(n log n) | O(n log n) | O(n log n) | Yes |
| Quicksort | O(n log n) | O(n log n) | O(n^2) | No |
| Heapsort | O(n log n) | O(n log n) | O(n log n) | No |
| Counting sort (range k) | O(n + k) | O(n + k) | O(n + k) | Yes |
| Radix sort | O(d * (n + k)) | O(d * (n + k)) | O(d * (n + k)) | Yes |
Most language standard library sorts use a hybrid of merge sort and insertion sort (Timsort) and are O(n log n) worst-case stable.
Searching
Linear search: O(n)
Binary search on sorted array: O(log n)
Ternary search on unimodal function: O(log n)Binary search is the answer whenever you can phrase the problem as “find the smallest x such that P(x) is true” on a monotone predicate.
Rules of Thumb for n
These ranges assume roughly one second on a modern CPU with vanilla code.
nup to 10: anything works, even O(n!).nup to 20: O(2^n) backtracking is fine.nup to 500: O(n^3) is fine.nup to 5,000: O(n^2) is fine.nup to 1,000,000: O(n log n) and O(n) are fine.nup to 100,000,000: O(n) only, with constant factors in mind.
If you blow through the budget, look for a smarter algorithm rather than tightening constants.
Space Complexity Reminders
Auxiliary space matters as much as time in memory-constrained interviews.
- Recursive DFS uses
O(h)stack space wherehis the depth. - Iterative DP often needs only
O(width)rolling space rather than the full table. - Hash maps add overhead per entry beyond the raw data.
Wrapping Up
Treat this cheatsheet as a checklist, not a wall of text. Recall a row at random and try to derive the number from first principles. Once you can do that for every row, you have not only memorized the cheatsheet — you have internalized the structures behind it. That is the difference between candidates who guess and candidates who reason.
Related articles
- DSA Big-O Notation: Time and Space Complexity Explained
A practical guide to Big-O notation — O(1), O(log n), O(n), O(n log n), O(n^2), and beyond, with code examples, best/average/worst case, and a brief look at amortized and space complexity.
- DSA Find Median from Data Stream — Two-Heaps Pattern
Solve Find Median from Data Stream with two heaps. Learn the balance invariant, why it gives O(log n) inserts and O(1) median, and the common pitfalls.
- DSA Find Minimum in Rotated Sorted Array — Binary Search
Solve Find Minimum in Rotated Sorted Array in logarithmic time with a modified binary search. Learn the pivot-finding invariant, edge cases, and how to extend the pattern to related problems.
- DSA Fizz Buzz — A Clean, Extensible Solution
Solve Fizz Buzz with clean code and explore the string-concatenation pattern that avoids nested if-else. Python, Java, C++, and complexity analysis included.