Consider the following Python function: def find_max (L): max = 0 for x in L if
ID: 3785910 • Letter: C
Question
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.
a)In asymptotic notation, determine the best case running time as function of n.
b)In asymptotic notation, determine the worst case running time as function of n.
c)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.
Explanation / Answer
Q.) a.)
a.) The given function will have best case, if the first element is maximum. But the given for loop will iterate 0 to end of list, i.e., n times and there will be n comparisons irrespective of the data. So asymptotically it will run in order of n. So, best case running time is Big-omega(n).
b.) The given function will have worst case, if data is arranged in increasing order which leads to n times updation of max as each time condition inside for loop will run n times for sure. But asymptotically it will run in order of n. So, worst case running time is O(n).
Note: Since asymptotically best case and worst case are equal, therefore asymptotically average case running time is Big-Theta(n).
c.) If L is sorted. The algo, will be:
def find_max(L):
max = L[0]
if(max < L[-1]) :
max = L[-1]
return max
The above algo. will check for max value only 2 places, starting element of list and end of list.
So, asymptotically it will take order of 1 which takes asymptotically less time than the given algorithm.
The given algorithm will be useless in case of sorted list as max number will be either at the starting or at end of the list. So, there is no reason to compare value for n times.
Hope it helps, do give your response.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.