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 $$ notation. Justify your answer.