Here’s a handy Big O Notation Cheatsheet for common data structures and algorithms:
🧠 Big O Complexity Basics
| Complexity | Name | Example |
|---|---|---|
| O(1) | Constant | Accessing array index |
| O(log n) | Logarithmic | Binary search |
| O(n) | Linear | Loop through array |
| O(n log n) | Linearithmic | Merge sort, Quick sort (avg) |
| O(n²) | Quadratic | Nested loops, Bubble sort |
| O(2ⁿ) | Exponential | Recursive Fibonacci |
| O(n!) | Factorial | Traveling salesman |
📚 Data Structures
🔹 Arrays
| Operation | Time Complexity |
|---|---|
| Access | O(1) |
| Search | O(n) |
| Insert/Delete | O(n) |
🔹 Linked List (Singly/Doubly)
| Operation | Time Complexity |
|---|---|
| Access/Search | O(n) |
| Insert/Delete | O(1) (at head/tail) |
🔹 Stack / Queue
| Operation | Time Complexity |
|---|---|
| Push/Pop | O(1) |
| Enqueue/Dequeue | O(1) |
🔹 Hash Table
| Operation | Average | Worst |
|---|---|---|
| Search | O(1) | O(n) |
| Insert/Delete | O(1) | O(n) |
🔹 Binary Search Tree (BST)
| Operation | Average | Worst |
|---|---|---|
| Search/Insert/Delete | O(log n) | O(n) |
🔹 Balanced BST (AVL, Red-Black)
| Operation | Time Complexity |
|---|---|
| Search/Insert/Delete | O(log n) |
🔹 Heap (Min/Max Heap)
| Operation | Time Complexity |
|---|---|
| Insert | O(log n) |
| Delete Min/Max | O(log n) |
| Find Min/Max | O(1) |
🔹 Graph (Adjacency List)
| Operation | Time Complexity |
|---|---|
| Add Vertex | O(1) |
| Add Edge | O(1) |
| Search (DFS/BFS) | O(V + E) |
🔍 Sorting Algorithms
| Algorithm | Best | Average | Worst | Space |
|---|---|---|---|---|
| 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) |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) |
| Quick Sort | O(n log n) | O(n log n) | O(n²) | O(log n) |
| Heap Sort | O(n log n) | O(n log n) | O(n log n) | O(1) |
| Radix Sort | O(nk) | O(nk) | O(nk) | O(n + k) |
