Given an unsorted array A of n distinct integers and an integer k$,$ you need to return the k smallest integers In the array in sorted order, where k may be any infeger between $1$ and n$.$ Suppose that you have the following three algorithms to solve this problem.

A$1$: Sort the array in increasing order, then list the first k integers after sorting.

A$2$: Build a min$-$heap from these n integers, then call Extract$-$Min k times.

A$3$: Use the linear time selection algorithm to find the k$-$th smallest integer in the array, then partition the array about that number to obtain the k smallest numbers in the array, and finally sort the k smallest numbers.

Assume that you are using mergesort as your sorting algorithm, and use the linear time build heap algorithm to build the heap.Let T$1($n$,$ k$)$ denote the worst$-$case running time of Algorithm A$1.$Let T$2($n$,$ k$)$ denote the worst$-$case running time of Algorithm A$2.$Let T$3($n$,$ k$)$ denote the worst$-$case running time of Algorithm A$3.$Analyze the worst$-$case running times of the algorithms.

$1.$ What is the asymptotic notation of T$1($n$,$ K$)?$ Justify your answer.

$2.$ What is the asymptotic notation of T$2($n$,$ K$)?$ Justify your answer.

$3.$ What is the asymptotic notation of T$3($n$,$ K$)?$ Justify your answer.

$4.$ Assume that worst$-$case time complexity is the only metric in choosing algorithms. Among the three algorithms, which algorithm would you choose to solve this problem? Justify why.