| Topic | Time Complexity | Space Complexity | Important Points |
|---|---|---|---|
| Sequential Search | O(n) | O(1) | Linear search through a list. |
| Binary Search | O(log n) | O(1) | Works on sorted arrays. |
| Merge Sort | O(n log n) | O(n) | Divide and conquer approach. |
| Quick Sort | O(n log n) avg, O(n²) worst | O(log n) | Pivot selection is crucial. |
| Euclid's Algorithm | O(log min(a, b)) | O(1) | Finds the greatest common divisor (GCD) of two numbers. |
| Consecutive Integer Checking Algorithm | O(min(a, b)) | O(1) | Iteratively checks for the GCD of two numbers. |
| Middle-School Procedure | O(n²) | O(1) | Finds GCD using prime factorization. |
| Algorithm | Time Complexity | Space Complexity | Important Points |
|---|---|---|---|
| Naive String Matching | O(n * m) | O(1) | Brute-force approach. |
| Rabin-Karp | O(n + m) | O(1) | Uses hashing for pattern matching. |
| Knuth-Morris-Pratt (KMP) | O(n + m) | O(m) | Preprocesses the pattern to avoid redundant comparisons. |
| Algorithm | Time Complexity | Space Complexity | Important Points |
|---|---|---|---|
| Strassen's Matrix Multiplication | O(n^2.81) | O(n^2) | Faster than standard O(n³) matrix multiplication. |
| Closest Pair Problem | O(n log n) | O(n) | Finds the closest pair of points in a plane. |
| Algorithm | Time Complexity | Space Complexity | Important Points |
|---|---|---|---|
| Depth-First Search (DFS) | O(V + E) | O(V) | Uses a stack, explores as far as possible. |
| Breadth-First Search (BFS) | O(V + E) | O(V) | Uses a queue, explores all neighbors at the current depth. |
| Dijkstra's Algorithm | O(V²) or O(E log V) | O(V) | Finds the shortest path in a graph with non-negative weights. |
| Algorithm | Time Complexity | Space Complexity | Important Points |
|---|---|---|---|
| Insertion Sort | O(n²) | O(1) | Efficient for small datasets. |
| Heapsort | O(n log n) | O(1) | In-place sorting with a binary heap. |
| Counting Sort | O(n + k) | O(k) | Works for small integer ranges. |
| Radix Sort | O(n * k) | O(n + k) | Sorts numbers digit by digit. |
| Bucket Sort | O(n + k) | O(n + k) | Distributes elements into buckets and sorts them. |
| Selection Sort | O(n²) | O(1) | Repeatedly selects the smallest element. |
| Algorithm | Time Complexity | Space Complexity | Important Points |
|---|---|---|---|
| Balanced Search Tree (General) | O(log n) | O(n) | Maintains balance for efficient operations. |
| AVL Tree | O(log n) | O(n) | Self-balancing binary search tree. |
| Red-Black Tree | O(log n) | O(n) | Balanced tree with color properties. |
| Algorithm | Time Complexity | Space Complexity | Important Points |
|---|---|---|---|
| Hashing (Average Case) | O(1) | O(n) | Efficient for insertion, deletion, and lookup. |
| Hashing (Worst Case) | O(n) | O(n) | Occurs due to hash collisions. |
| Algorithm | Time Complexity | Space Complexity | Important Points |
|---|---|---|---|
| Knapsack Problem (0/1) | O(n * W) | O(n * W) | Dynamic Programming solution for the 0/1 Knapsack problem. |
| Traveling Salesman Problem (TSP) | O(n² * 2^n) | O(n * 2^n) | Dynamic Programming solution for TSP. |
| The Assignment Problem | O(n³) | O(n²) | Hungarian Algorithm for solving the assignment problem. |
| Brute Force (Closest Pair) | O(n²) | O(1) | Compares all pairs of points to find the closest pair. |
| Brute Force (Convex Hull) | O(n³) | O(n) | Checks all possible lines to form the convex hull. |
| Brute Force (Exhaustive Search) | O(2^n) | O(n) | Explores all possible solutions. |
| Voronoi Diagrams | O(n log n) | O(n) | Computes the Voronoi diagram using Fortune's algorithm. |