Maximum Number In List
You have a list \(a = \left[a,a,\ldots,a[n-1]\right],\) and you want to find the maximum number in the list. You come up with the following convoluted algorithm:
- Compare each pair of consecutive elements in the list, and keep track of the index of the smaller of the two.
- After going through the entire list, delete all of the elements which were the smallest (or equally smallest) in a pair. (You can assume that this step takes no additional computation.)
- Repeat the process on the new list until only 1 element remains: this must be the largest element!
Of course, this algorithm has a best-case runtime of \(O(n)\); for example, if the list were sorted, we would succeed in just one iteration with \(n-1\) comparisons! What is the worst-case runtime of this algorithm?