You have a list $a = \left[a[0],a[1],\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?

×

Problem Loading...

Note Loading...

Set Loading...