Maximum Number In List

You have a list a=[a[0],a[1],,a[n1]],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)O(n); for example, if the list were sorted, we would succeed in just one iteration with n1n-1 comparisons! What is the worst-case runtime of this algorithm?

×

Problem Loading...

Note Loading...

Set Loading...