In this chapter, we learned about a few of the most commonly used search algorithms. See the following table for a comparison of their relative performances. This will give you a better understanding when you come to choose which algorithm to use yourself:
| Algorithm | Performance |
| Linear Search | O(n) |
| Binary Search | O(log n) |
| Jump Search | O(√n) |
| Exponential Search | O(log n) |
Here, n is the size of the collection.
In addition to item search algorithms, we've also covered a few commonly used pattern matching algorithms. Here is a comparison of their relative performance:
| Algorithm | Performance |
| Naive Pattern Search | O(m * n) |
| Rabin-Karp Search | O(m * n) |
| Knuth-Morris-Prath Search | O(m) + O(k) = O(n + k) |
Here, m is the length of the text, n is the length of the pattern and k is the length of temporary array created for KMP search (the same as the pattern...