Your lecturer is a funny guy; given an unsorted list of integer numbers of n elements,...

 

Transcribed Image Text:

Your lecturer is a funny guy; given an unsorted list of integer numbers of n elements, and to find the largest number in the list, he will first initialize a variable, let's say max, to the smallest possible number an integer can be, and randomly select an element (a number) from the unsorted list. Check if this number is greater than the variable max. If it is, he will set the variable max to the number. Next, he will discard the number from the list and create a new list. The new list now has n - 1 elements. He will continue with the same process on the n-1 elements list until the unsorted list has no more element. When this happens, the variable max will contain the largest number in the list. (a) Write in pseudocode a recursive implementation of the described algorithm. (b) Analyse the asymptotic complexity of the algorithm. Give the worst-case, average- case and best-case running time in terms of 8 notation. Justify your answer. Your lecturer is a funny guy; given an unsorted list of integer numbers of n elements, and to find the largest number in the list, he will first initialize a variable, let's say max, to the smallest possible number an integer can be, and randomly select an element (a number) from the unsorted list. Check if this number is greater than the variable max. If it is, he will set the variable max to the number. Next, he will discard the number from the list and create a new list. The new list now has n - 1 elements. He will continue with the same process on the n-1 elements list until the unsorted list has no more element. When this happens, the variable max will contain the largest number in the list. (a) Write in pseudocode a recursive implementation of the described algorithm. (b) Analyse the asymptotic complexity of the algorithm. Give the worst-case, average- case and best-case running time in terms of 8 notation. Justify your answer.