| Name | Efficiency | Notes |
|---|---|---|
| Towers of Hanoi | O(2n) | |
| Selection Sort | O(n2) | |
| Bubble Sort | O(n2) | |
| String Matching | O(m * n) | m = text, n = pattern |
| Closest Pair | O(n2) | |
| Convex Hull | O(n3) | |
| Travelling Salesman Problem | O(n!) | |
| Cheapest Job Assignment | O(n!) | |
| Knapsack | O(2n) | |
| Matrix Multiplication | O(n3) | |
| Polynomial Evaluation | O(n2) |
| Name | Efficiency | Notes |
|---|---|---|
| Insertion Sort | O(n2 | Decrease by constant |
| Fake Coin Problem | O(logn) | Decrease by constant factor |
| Euclid's GCD | O(logn) | Variable size decrease |
| Interpolation Sort | O(loglogn+1) average, O(n) worst |
| Name | Efficiency | Notes |
|---|---|---|
| Matrix Multiplication | O(n3) | |
| Strassen Method | O(n2.8) | 7T(n/2) + n2 recurrence |
| Closest Pair | O(nlogn) | Presorting is O(logn), every other step is O(n) |
| Convex Hull | O(nlogn) average, O(n2) worst | |
| Binomial Coefficient | O(2n) |
| Name | Efficiency | Notes |
|---|---|---|
| Horner's Rule | O(n) | Polynomial evaluation |
| Type | Worst Case | Best Case | Notes |
|---|---|---|---|
| Horspool | O(nm) | Θ(n) | Faster on average than brute-force, often at least as efficient as Boyer-Moore |
| Binomial Coefficient | O(n2) | O(n * k) | |
| Warshall | O(n3) | O(n3) | The space complexity can possibly be O(n2) |
| Floyd | O(n3) | O(n3) |