Consider the following Python function def findmax L max 0

Consider the following Python function: def find_max (L): max = 0 for x in L: if x > max: max = x return max Suppose list L has n elements. In asymptotic notation, determine the best case running time as function of n In asymptotic notation, determine the worst case running time as function of n Now, assume L is sorted. Give an algorithm that takes asymptotically less time than the above algorithm, but performs the same function. Prove that your algorithm is correct, and explain why this algorithm is useless.

Solution

(a) The best case running time is (n)
(b) The worst case running time is also (n)
(c) If L is already sorted, the the max element is the last element in the list. The function can return L[n-1]. This algorithm is useless as to sort the list it will take O(nlogn) time to sort itself. So total time to find the max element will be O(nlogn).