Big O Categories
| Big-O | Name | Speed | Example |
|---|
| O(1) | Constant | Best | Array index lookup |
| O(log n) | Logarithmic | Great | Binary search |
| O(n) | Linear | Good | Single loop through array |
| O(n log n) | Linearithmic | Okay | Merge sort, Quick sort (avg) |
| O(n²) | Quadratic | Slow | Nested loops, Bubble sort |
| O(n³) | Cubic | Slower | Triple nested loops |
| O(2ⁿ) | Exponential | Horrible | Brute-force subsets |
| O(n!) | Factorial | Worst | Generating all permutations |
Common Data Structure Operations
| Data Structure | Access | Search | Insert | Delete |
|---|
| Array | O(1) | O(n) | O(n) | O(n) |
| Stack / Queue | O(n) | O(n) | O(1) | O(1) |
| Linked List | O(n) | O(n) | O(1) | O(1) |
| Hash Map | O(1) avg | O(1) avg | O(1) avg | O(1) avg |
| BST (balanced) | O(log n) | O(log n) | O(log n) | O(log n) |
| Heap | O(1) peek | O(n) | O(log n) | O(log n) |
Common Sorting Complexities
| Algorithm | Best | Average | Worst | Space | Stable? |
|---|
| Bubble Sort | O(n) | O(n²) | O(n²) | O(1) | Yes |
| 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 |
Python sorted() (Timsort) | O(n) | O(n log n) | O(n log n) | O(n) | Yes |
P vs NP
- P — Problems that can be solved in polynomial time (e.g., sorting, binary search)
- NP — Problems whose solutions can be verified in polynomial time, but not necessarily solved fast (e.g., Sudoku, Travelling Salesman)
- P ⊆ NP — Every problem solvable in polynomial time can also be verified in polynomial time
- P = NP? — The biggest unsolved question in computer science
For interviews: just know that NP-hard problems have no known efficient solution — you typically use approximations or heuristics.
Space Complexity Notes
- O(1) — In-place (only a few variables, no extra data structures)
- O(log n) — Recursion stack depth for divide-and-conquer on balanced input
- O(n) — Storing a copy of the input, or recursion on a linear structure
- O(n²) — Storing a 2D grid/DP table