Big O Cheat Sheet
Quick reference for time and space complexity of common algorithms and data structures. Essential for coding interviews at FAANG and other tech companies.
Complexity Scale (Best to Worst)
Data Structure Operations
| Data Structure | Access | Search | Insert | Delete | Space |
|---|---|---|---|---|---|
| Array | O(1) | O(n) | O(n) | O(n) | O(n) |
| Stack | O(n) | O(n) | O(1) | O(1) | O(n) |
| Queue | O(n) | O(n) | O(1) | O(1) | O(n) |
| Linked List | O(n) | O(n) | O(1) | O(1) | O(n) |
| Hash Table | O(1) | O(1) | O(1) | O(1) | O(n) |
| Binary Search Tree | O(log n) | O(log n) | O(log n) | O(log n) | O(n) |
| AVL Tree | O(log n) | O(log n) | O(log n) | O(log n) | O(n) |
| Heap | O(1) | O(n) | O(log n) | O(log n) | O(n) |
* Average case complexity shown. Worst case may differ (e.g., Hash Table worst case is O(n)).
Sorting Algorithms
| Algorithm | Best | Average | Worst | Space |
|---|---|---|---|---|
| Quick Sort | O(n log n) | O(n log n) | O(n²) | O(log n) |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) |
| Heap Sort | O(n log n) | O(n log n) | O(n log n) | O(1) |
| Bubble Sort | O(n) | O(n²) | O(n²) | O(1) |
| Insertion Sort | O(n) | O(n²) | O(n²) | O(1) |
| Selection Sort | O(n²) | O(n²) | O(n²) | O(1) |
| Counting Sort | O(n + k) | O(n + k) | O(n + k) | O(k) |
| Radix Sort | O(nk) | O(nk) | O(nk) | O(n + k) |
Common Code Patterns
for (let i = 0; i < n; i++)for i... for j...while (left < right) mid = (left + right) / 2sort() + binary searchmap.get(key)while (left < right)fixed or variable windowVisit all vertices and edgesBacktracking / bit manipulationBacktracking with swapsInterview Tips
Always state complexity: After explaining your solution, mention both time and space complexity.
Consider trade-offs: Sometimes O(n) space can reduce O(n²) time to O(n). Discuss these trade-offs.
Drop constants: O(2n) simplifies to O(n). Focus on the dominant term.
Amortized analysis: Some operations (like dynamic array resize) are O(1) amortized even if occasionally O(n).
Need help during your coding interview?
Get AI-powered real-time assistance with Interview Solver-live hints, solutions, and explanations during your actual coding interviews.