📋 DSA Cheatsheet
Quick reference for algorithms, data structures, and problem-solving patterns
Big O Notation Cheatsheet
| Complexity | Name | Example Operations | Rating |
|---|---|---|---|
| O(1) | Constant | Array access, hash table lookup, math operations | Excellent |
| O(log n) | Logarithmic | Binary search, balanced BST operations | Excellent |
| O(n) | Linear | Single loop, array traversal | Good |
| O(n log n) | Linearithmic | Merge sort, quick sort, heap sort | Fair |
| O(n²) | Quadratic | Nested loops, bubble sort, selection sort | Bad |
| O(2ⁿ) | Exponential | Recursive fibonacci, power set | Horrible |
| O(n!) | Factorial | Permutations, traveling salesman (brute force) | Horrible |
Quick Rules for Big O
- 1.Drop constants: O(2n) → O(n), O(500) → O(1)
- 2.Drop non-dominant terms: O(n² + n) → O(n²)
- 3.Different inputs = different variables: Two separate loops with different inputs is O(a + b), not O(n)
- 4.Nested loops: Generally multiply complexities: O(n) × O(n) = O(n²)