# Big-O Cheat Sheet: Time and Space Complexity Guide

Source: https://www.techinterview.org/big-o-cheat-sheet/
Updated: 2026-07-03 · techinterview.org

**TL;DR —** Big-O notation describes how an algorithm's running time or memory use grows as its input gets larger, capturing the worst-case upper bound rather than an exact speed. Ordered from fastest to slowest, the common time complexities are O(1) constant, O(log n) logarithmic, O(n) linear, O(n log n) linearithmic, O(n²) quadratic, and O(2ⁿ) exponential. Space complexity uses the same notation to measure the extra memory an algorithm needs beyond its input.

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 + str2` in most languages is O(n), not O(1)

- `list.contains()` is O(n) for list, O(1) for set

- `list.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](/post/3233474160/coding-interview-two-pointers-sliding-window-patterns-array-string-problems-fast-slow-pointer-variable-window/)

- **Need to try all possibilities?** → [Backtracking](/algorithm-patterns-cheat-sheet/) 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.