| Notation | Meaning | Example | Common Algorithms |
|---|---|---|---|
| O(1) | Constant time | Accessing array element | Array access, hash table lookup |
| O(log n) | Logarithmic time | Binary search | Binary search, balanced tree operations |
| O(n) | Linear time | Linear search | Linear search, traversing array |
| O(n log n) | Linearithmic | Efficient sorting | Merge sort, quick sort average case |
| O(n²) | Quadratic time | Bubble sort | Bubble sort, selection sort |
| O(2ⁿ) | Exponential time | Tower of Hanoi | Recursive algorithms without memoization |
| O(n!) | Factorial time | Traveling salesman | Permutations, brute force |
| Algorithm | Time Complexity (Avg) | Time Complexity (Worst) | Space Complexity | Stable | Best Use Case |
|---|---|---|---|---|---|
| Bubble Sort | O(n²) | O(n²) | O(1) | Yes | Small datasets, educational purposes |
| Selection Sort | O(n²) | O(n²) | O(1) | No | Small datasets, minimal memory writes |
| Insertion Sort | O(n²) | O(n²) | O(1) | Yes | Small datasets, nearly sorted data |
| Merge Sort | O(n log n) | O(n log n) | O(n) | Yes | Stable sort, guaranteed performance |
| Quick Sort | O(n log n) | O(n²) | O(log n) | No | General purpose, in-place sorting |
| Heap Sort | O(n log n) | O(n log n) | O(1) | No | Guaranteed O(n log n), in-place |
| Counting Sort | O(n + k) | O(n + k) | O(k) | Yes | Small integer keys, limited range |
| Radix Sort | O(d(n + k)) | O(d(n + k)) | O(n + k) | Yes | Fixed-length keys, integers or strings |
| Algorithm | Time Complexity | Space Complexity | Requirements | Best Use Case |
|---|---|---|---|---|
| Linear Search | O(n) | O(1) | Unsorted array | Small arrays, unsorted data |
| Binary Search | O(log n) | O(1) | Sorted array | Large sorted arrays |
| Jump Search | O(√n) | O(1) | Sorted array | Block-based searching |
| Interpolation Search | O(log log n) | O(1) | Sorted array, uniformly distributed | Uniformly distributed sorted data |
| Exponential Search | O(log n) | O(1) | Sorted array | Unbounded or infinite arrays |
| Algorithm | Purpose | Time Complexity | Space Complexity | Best Use Case |
|---|---|---|---|---|
| BFS | Shortest path in unweighted graph | O(V + E) | O(V) | Shortest path, level-order traversal |
| DFS | Traverse graph, detect cycles | O(V + E) | O(V) | Topological sort, cycle detection |
| Dijkstra | Shortest path in weighted graph | O((V + E) log V) | O(V) | Non-negative weights, single source |
| Bellman-Ford | Shortest path with negative weights | O(VE) | O(V) | Negative weights, detect negative cycles |
| Floyd-Warshall | All-pairs shortest paths | O(V³) | O(V²) | Small graphs, all-pairs paths |
| Kruskal | Minimum Spanning Tree | O(E log E) | O(E) | Sparse graphs, disjoint sets |
| Prim | Minimum Spanning Tree | O(E log V) | O(V) | Dense graphs, priority queue |
| Topological Sort | Order for dependencies | O(V + E) | O(V) | Task scheduling, dependencies |
| Structure | Access | Search | Insertion | Deletion | Space | Best Use Case |
|---|---|---|---|---|---|---|
| Array | O(1) | O(n) | O(n) | O(n) | O(n) | Random access, fixed size |
| Stack | O(n) | O(n) | O(1) | O(1) | O(n) | LIFO operations, function calls |
| Queue | O(n) | O(n) | O(1) | O(1) | O(n) | FIFO operations, BFS |
| Singly Linked List | O(n) | O(n) | O(1) | O(1) | O(n) | Dynamic size, frequent insertions/deletions |
| Doubly Linked List | O(n) | O(n) | O(1) | O(1) | O(n) | Bi-directional traversal |
| Hash Table | N/A | O(1) | O(1) | O(1) | O(n) | Fast lookups, key-value pairs |
| Binary Search Tree | O(log n) | O(log n) | O(log n) | O(log n) | O(n) | Sorted data, range queries |
| AVL Tree | O(log n) | O(log n) | O(log n) | O(log n) | O(n) | Balanced tree, guaranteed performance |
| Heap | O(1) | O(n) | O(log n) | O(log n) | O(n) | Priority queue, heap sort |
| Pattern | Problem Type | Approach | Example Problems |
|---|---|---|---|
| Grid DP | 2D path finding | 2D table, fill row by row | Unique paths, min path sum |
| Knapsack | Optimization with constraints | Maximize value within capacity | 0/1 knapsack, unbounded knapsack |
| LIS | Longest increasing subsequence | Compare with previous elements | Longest increasing subsequence |
| Palindromes | Palindrome problems | Expand around centers or DP table | Longest palindromic substring |
| Partition | Divide into groups | Try all possible partitions | Partition to equal sum subsets |
| Bit Manipulation | Subset problems | Use bits to represent subsets | Generate all subsets |
| Algorithm | Purpose | Time Complexity | Space Complexity | Best Use Case |
|---|---|---|---|---|
| KMP | Pattern matching | O(n + m) | O(m) | Pattern matching with preprocessing |
| Rabin-Karp | Pattern matching | O(n + m) | O(1) | Multiple pattern search |
| Z Algorithm | Pattern matching | O(n) | O(n) | Find all occurrences efficiently |
| Trie | Prefix operations | O(m) | O(ALPHABET_SIZE * N * M) | Autocomplete, spell checker |
| Manacher | Longest palindromic substring | O(n) | O(n) | Linear palindrome detection |
| Technique | Description | When to Use | Example Problems |
|---|---|---|---|
| Greedy | Make locally optimal choices | Optimal substructure, greedy choice property | Activity selection, Huffman coding |
| Divide & Conquer | Break into subproblems | Problems that can be divided | Merge sort, binary search |
| Dynamic Programming | Store results of subproblems | Overlapping subproblems | Fibonacci, knapsack |
| Backtracking | Try all possibilities | Constraint satisfaction problems | N-Queens, Sudoku |
| Two Pointers | Two pointers in data structure | Sorted arrays, linked lists | Two sum, palindrome check |
| Sliding Window | Fixed/variable size window | Subarray/string problems | Max sum subarray, anagram |
| BFS | Level-by-level exploration | Shortest path, tree problems | Level order traversal, shortest path |
| DFS | Deep exploration | Graph/tree traversal | Connected components, cycle detection |
| Traversal | Order | Implementation | Use Case |
|---|---|---|---|
| Preorder | Root → Left → Right | Process root first | Copy tree, expression evaluation |
| Inorder | Left → Root → Right | Process root between subtrees | Binary search tree (sorted order) |
| Postorder | Left → Right → Root | Process root last | Delete tree, expression evaluation |
| Level Order | Level by level | Use queue | BFS, print tree level by level |
| Algorithm | Purpose | Time Complexity | Space Complexity |
|---|---|---|---|
| Binary Search | Find element in sorted array | O(log n) | O(1) |
| Fast Power | Compute a^n efficiently | O(log n) | O(1) |
| Euclidean Algorithm | Find GCD | O(log min(a,b)) | O(1) |
| Extended Euclidean | Find GCD and coefficients | O(log min(a,b)) | O(1) |
| Sieve of Eratosthenes | Find all primes up to n | O(n log log n) | O(n) |
| Union-Find | Disjoint set operations | O(α(n)) amortized | O(n) |
| Topological Sort | Order vertices with dependencies | O(V + E) | O(V) |
| Kadane's Algorithm | Maximum subarray sum | O(n) | O(1) |