Big-O Cheat Sheet
Complete guide to time and space complexity for technical interviews
What is Big-O Notation?
Big-O notation describes the worst-case performance of an algorithm as the input size grows. It helps compare algorithm efficiency and is crucial for technical interviews.
Key Principle:
Big-O describes the growth rate, not exact runtime. We care about behavior as n → ∞.
Common Time Complexities (Ranked)
| Big-O | Name | Example | n=10 | n=100 | n=1000 |
|---|---|---|---|---|---|
| O(1) | Constant | Array access, hash lookup | 1 | 1 | 1 |
| O(log n) | Logarithmic | Binary search, balanced tree | 3 | 7 | 10 |
| O(n) | Linear | Linear search, array traversal | 10 | 100 | 1,000 |
| O(n log n) | Linearithmic | Merge sort, quicksort (avg) | 30 | 664 | 9,966 |
| O(n²) | Quadratic | Bubble sort, nested loops | 100 | 10,000 | 1,000,000 |
| O(n³) | Cubic | Triple nested loops | 1,000 | 1,000,000 | 1,000,000,000 |
| O(2^n) | Exponential | Fibonacci recursion, subsets | 1,024 | 1.27×10³⁰ | ∞ (impractical) |
| O(n!) | Factorial | Permutations, traveling salesman | 3,628,800 | ∞ | ∞ |
Rule of Thumb for Interviews
- n ≤ 10: O(n!) is acceptable
- n ≤ 20: O(2^n) is acceptable
- n ≤ 500: O(n³) is acceptable
- n ≤ 5,000: O(n²) is acceptable
- n ≤ 1,000,000: O(n log n) or better required
- n > 1,000,000: O(n) or O(log n) required
Data Structure Operations
Array
- Access: O(1)
- Search: O(n)
- Insert (end): O(1) amortized
- Insert (beginning): O(n)
- Delete: O(n)
- Space: O(n)
Hash Table
- Search: O(1) average, O(n) worst
- Insert: O(1) average, O(n) worst
- Delete: O(1) average, O(n) worst
- Space: O(n)
Binary Search Tree (Balanced)
- Search: O(log n)
- Insert: O(log n)
- Delete: O(log n)
- Space: O(n)
Heap (Min/Max)
- Find Min/Max: O(1)
- Insert: O(log n)
- Delete Min/Max: O(log n)
- Build Heap: O(n)
- Space: O(n)
Linked List
- Access: O(n)
- Search: O(n)
- Insert (beginning): O(1)
- Insert (end): O(n) or O(1) with tail pointer
- Delete: O(n)
- Space: O(n)
Sorting Algorithms
| Algorithm | Best | Average | Worst | Space | Stable? |
|---|---|---|---|---|---|
| Quick Sort | 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 |
| Heap Sort | O(n log n) | O(n log n) | O(n log n) | O(1) | No |
| Bubble Sort | O(n) | O(n²) | O(n²) | O(1) | Yes |
| Insertion Sort | O(n) | O(n²) | O(n²) | O(1) | Yes |
| Selection Sort | O(n²) | O(n²) | O(n²) | O(1) | No |
Calculating Big-O: Rules
1. Drop Constants
O(2n) → O(n)
O(500) → O(1)
2. Drop Lower Order Terms
O(n² + n) → O(n²)
O(n + log n) → O(n)
3. Different Inputs = Different Variables
for (int i = 0; i < a.length; i++) { // O(a)
for (int j = 0; j < b.length; j++) { // O(b)
...
}
}
// Time: O(a * b), NOT O(n²)
4. Amortized Analysis
Dynamic array append is O(1) amortized, even though occasional resize is O(n).
Space Complexity Rules
- Recursion: O(depth) for call stack. Each pending call keeps a frame, so a recursion that runs n levels deep uses O(n) stack space even when the body allocates nothing else.
- Iteration: Usually O(1) unless creating new data. A loop that fills a new array or hash map of size n pays O(n) for what it stores, not for the loop itself.
- Memoization: Space = Time (usually). You cache every subproblem result to avoid recomputing it, so the table grows to match the number of distinct states you visit.
- In-place: O(1) extra space. The algorithm rewrites the input directly instead of allocating a copy; reversing an array by swapping the two ends inward is the standard example.
Common Interview Pitfalls
Mistake: Assuming All Operations Are O(1)
str1 + str2in most languages is O(n), not O(1)list.contains()is O(n) for list, O(1) for setlist.remove(element)is O(n)
Mistake: Not Considering Space Complexity
An O(n) time, O(n) space solution may be worse than O(n log n) time, O(1) space for memory-constrained systems.
Mistake: Premature Optimization
Start with brute force, explain complexity, then optimize. Don’t jump to complex O(n) solution if O(n log n) is acceptable.
Quick Reference: When to Use What
- Need fast lookup? → Hash Table (O(1))
- Need sorted order? → BST (O(log n)) or sorted array with binary search
- Need to find min/max quickly? → Heap (O(1) find, O(log n) insert/delete)
- Need to track frequency? → Hash Map
- Need sliding window? → Deque or Two Pointers
- Need to try all possibilities? → Backtracking or DP
Practice Problems by Complexity
O(1) – Constant
- Check if number is even/odd. A single modulo or bit check (n & 1) with no loop, so the work never grows with the size of n.
- Access array element by index. The index becomes a fixed memory offset, so arr[500] costs exactly what arr[0] costs.
- Swap two variables. A fixed number of assignments regardless of the data, which is why temp-variable and tuple swaps are both O(1).
O(log n) – Logarithmic
- Binary search in sorted array. Each comparison halves the remaining range, so a million elements resolve in about 20 steps; interviewers watch that your low/high/mid math avoids an infinite loop or an off-by-one.
- Find element in balanced BST. You drop one level per comparison and a balanced tree’s height is log n, but the word “balanced” matters — a skewed tree degrades to O(n).
- Power function (x^n) using fast exponentiation. Squaring the base while halving the exponent turns n multiplications into log n.
O(n) – Linear
- Find maximum in unsorted array. You must look at every element once, since any value you skip could be the largest, so a single pass is optimal.
- Check if array contains duplicates (with hash set). One pass that adds each value to a set and checks membership first; this is the classic time-for-space trade of O(n) time for O(n) memory.
- Reverse a linked list. Walk the nodes once and repoint each next to the previous node; a frequent follow-up asks you to do it in place with three pointers instead of a new list.
O(n log n) – Linearithmic
- Merge sort, quicksort (average). The n log n comes from linear work (merging or partitioning) repeated across log n levels of splitting, and it is the floor for any comparison-based sort.
- Find kth largest element (using heap). Push all n values through a size-k heap at log k per operation; be ready to compare this with quickselect, which averages O(n).
- Sort characters in a string. Sorting is the usual first move for anagram and grouping problems, and that sort dominates the runtime at O(n log n).
O(n²) – Quadratic
- Find all pairs in array. A nested loop comparing every element with every other runs about n²/2 times; when asked to improve it, a hash map or a sort usually gets you to O(n) or O(n log n).
- Bubble sort, insertion sort. Both make nested passes over adjacent elements, and insertion sort is worth remembering because it drops to O(n) on nearly-sorted input.
- Check if one string is rotation of another (naive). The brute-force version tries every rotation offset and compares; the trick answer checks whether the second string is a substring of the first joined to itself.
Interview Tips
- Always State Complexity: After explaining your approach, clearly state: “This solution is O(n) time and O(1) space.”
- Optimize When Asked: If interviewer asks “Can you do better?”, identify the bottleneck and optimize that part.
- Consider Trade-offs: Sometimes O(n) time with O(n) space is better than O(n²) time with O(1) space. Ask about constraints.
- Don’t Guess: If unsure, work through small examples to determine complexity.
Master Big-O notation to succeed in technical interviews!
Where to actually drill these patterns
A cheat sheet tells you what the complexities are; it can’t build the recognition speed that gets you through a real interview. That comes from reps, and where you do them depends on your goal and your budget more than on which platform has the slickest marketing.
| Option | Best for | Worth paying when |
|---|---|---|
| Free practice (the open problem sets) | Volume and breadth | You’re self-directed and just need reps |
| Premium practice tiers | Company-tagged questions, sorted study | You’re targeting specific firms and value the filtering |
| Structured pattern courses | Learning the patterns from scratch | You keep failing to recognize which pattern a problem wants |
| System design courses | The design round specifically | You’re mid-to-senior and the design round is your weak spot |
If you already recognize patterns and just need volume, paying for practice buys you organization, not ability. If you stare at a problem and can’t tell whether it’s a sliding window or a heap, a structured course that teaches the patterns is the better spend. Match the tool to the gap you actually have.
