Lower Bounds: Optimal Solution to Searching/Sorting
- Identify which comparison-based searching/sorting algorithms are optimal.
- Understand and explain what lower bounds are for.
We will show that we cannot do better than binary search when it comes to searching, nor can we do better than linearithmic sorts (like merge sort) when it comes to sorting.
In other words, binary search and merge sort are optimal solutions to their respective problems.
Put differently, the lower bound on searching and sorting are $\Omega(\lg n)$ and $\Omega(n \lg n)$, respectively. This sets a precedent that cannot be outperformed by any comparison-based searching/sorting algorithm.
A lower bound for a problem is the worst-case running time of the best possible algorithm for that problem.