Big O reference for coding interviews
Time and space complexity, with the fine print.
34 data structures, algorithms, and patterns. Every bound says whether it is average, amortized, or worst case, and what it assumes.
What's here
Reference
- Topics
All 34 topics with search and filters. Each has its own page with code and pitfalls.
- Big O basics
What the notation means, a growth playground, and how to read the tables.
- Data structures
Arrays, hash tables, trees, heaps, tries, Union-Find, and graph representations.
- Sorting
Best, average, and worst case for 13 sorts, with the footnotes that matter.
- Search and graphs
Binary search, BFS, DFS, heaps, shortest paths, and spanning trees.
- Coding patterns
Typical costs of two pointers, sliding window, backtracking, and DP.
Tools
- Complexity lookup
Best, average, and worst case for one operation, with its caveat.
- Compare two algorithms
Time, space, stability, and trade-offs side by side.
- Visualizer
Step through searches, four sorts, BFS, and DFS one move at a time.
- Export and share
Markdown, CSV, printable cards, and PDFs.
Practice
- Roadmap
A suggested order for the topics, with prerequisites and progress.
- Quiz
Ten random questions with an explanation after each answer.
- Code challenges
Predict the time and space of short snippets in three languages.
- Revision sheet
The high-relevance topics on one printable page.
The ones you will be asked about
If you only memorize eight lines, make it these. Each links to the full explanation, and the lookup has the assumptions.
| Operation | Average | Worst |
|---|---|---|
| Hash table lookup, insert, delete | O(1) expected | O(n) |
| Binary search | O(log n) | O(log n) |
| Binary heap pop | O(log n) | O(log n) |
| Merge sort | O(n log n) | O(n log n) |
| Quicksort | O(n log n) | O(n²) |
| Breadth-first search | O(V + E) | O(V + E) |
| Dijkstra shortest path | O((V + E) log V) | O((V + E) log V) |
| Union-Find find and union | O(α(n)) amortized | O(α(n)) amortized |
The hash table worst case assumes many keys collide. Quicksort hits O(n²) when the pivot keeps splitting badly, such as a first-element pivot on sorted input. The colors match the strip at the top of every page: green is cheapest, dark red is exponential.
Found a bound that looks wrong? Open an issue with a source, and it gets fixed.