Big-O Cheat Sheet: Time & Space Complexity Reference

Big-O Cheat Sheet#

Big-O notation describes how an algorithm’s running time or memory grows as the input size n grows. It captures the worst-case trend, not the exact number of steps, so you can compare approaches without benchmarking. This page is a quick reference you can bookmark; each row links back to where the structure or algorithm shows up in the 60-day challenge.

The complexity classes, fastest to slowest#

Notation	Name	Rough meaning	Example
`O(1)`	Constant	Same work regardless of `n`	Array index lookup
`O(log n)`	Logarithmic	Halves the problem each step	Binary search
`O(n)`	Linear	Work grows with the input	Scanning an array
`O(n log n)`	Linearithmic	Sort-like divide and combine	Merge sort
`O(n²)`	Quadratic	Nested loops over the input	Bubble sort
`O(n³)`	Cubic	Triple nested loops	Naive all-pairs paths
`O(2ⁿ)`	Exponential	Doubles per added element	Naive subset generation
`O(n!)`	Factorial	All permutations	Brute-force travelling salesman

Rule of thumb for interviews: aim for O(n log n) or better on array/string problems, and treat O(2ⁿ)/O(n!) as a signal you need memoization, pruning, or a smarter pattern.

Data structure operations#

Average-case complexities (worst case in parentheses where it differs).

Data structure	Access	Search	Insert	Delete	Space
Array	`O(1)`	`O(n)`	`O(n)`	`O(n)`	`O(n)`
Dynamic array	`O(1)`	`O(n)`	`O(1)`*	`O(n)`	`O(n)`
Singly linked list	`O(n)`	`O(n)`	`O(1)`	`O(1)`	`O(n)`
Stack	`O(n)`	`O(n)`	`O(1)`	`O(1)`	`O(n)`
Queue	`O(n)`	`O(n)`	`O(1)`	`O(1)`	`O(n)`
Hash table	–	`O(1)` (`O(n)`)	`O(1)` (`O(n)`)	`O(1)` (`O(n)`)	`O(n)`
Binary search tree	`O(log n)` (`O(n)`)	`O(log n)` (`O(n)`)	`O(log n)` (`O(n)`)	`O(log n)` (`O(n)`)	`O(n)`
Balanced BST (AVL/Red-Black)	`O(log n)`	`O(log n)`	`O(log n)`	`O(log n)`	`O(n)`
Binary heap	`O(1)` peek	`O(n)`	`O(log n)`	`O(log n)`	`O(n)`

*Amortized: a dynamic array’s occasional resize is O(n), but averaged over many appends each push is O(1).

See these in the challenge: arrays, linked lists (Day 9), hash tables (Day 23), BSTs (Day 15), and heaps (Day 17).

Sorting algorithms#

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

Watch these run step by step in the sorting visualizer.

Graph algorithms#

For a graph with V vertices and E edges.

Algorithm	Time	Space
Breadth-first search (BFS)	`O(V + E)`	`O(V)`
Depth-first search (DFS)	`O(V + E)`	`O(V)`
Dijkstra (binary heap)	`O((V + E) log V)`	`O(V)`
Bellman-Ford	`O(V · E)`	`O(V)`
Floyd-Warshall	`O(V³)`	`O(V²)`
Topological sort	`O(V + E)`	`O(V)`

Interview pattern complexities#

Pattern	Typical time	When you reach for it
Two pointers	`O(n)`	Sorted arrays, pair/triplet sums
Sliding window	`O(n)`	Contiguous subarray/substring problems
Binary search	`O(log n)`	Sorted input or monotonic answer space
Hashing / frequency map	`O(n)`	Lookups, dedupe, counting
BFS/DFS traversal	`O(V + E)`	Trees and graphs
Dynamic programming	`O(n·states)`	Overlapping subproblems
Backtracking	`O(bᵈ)`	Enumerate combinations/permutations

How to reason about Big-O quickly#

Count nested loops over the input. One loop is O(n), a loop inside a loop is usually O(n²).
Halving is a logarithm. Each time you cut the problem in half, add a log n factor.
Drop constants and lower-order terms. O(2n + 5) is O(n); O(n² + n) is O(n²).
Recursion → recurrence. Merge sort does two half-size calls plus O(n) work per level. Writing that as a recurrence and solving it:
\(T(n) = 2\,T\!\left(\tfrac{n}{2}\right) + O(n) = O(n \log n)\)
Space counts too. Recursion uses stack space; an O(n) auxiliary array is O(n) space even if the time is better.

Ready to put this into practice? Start the free 60-day challenge or jump to interview prep.