You have a list 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 ; for example, if the list were sorted, we would succeed in just one iteration with comparisons! What is the worst-case runtime of this algorithm?