$3$ Divide&Conquer, Complexity Analysis $(10$p$)$

Consider the task of finding the smallest $k$ entries in an array of length $n.$ We could solve this in $O(nlogn)$

by first sorting the array $($e$.$g$.,$ via MergeSort$),$ and then returning the first $k$ entries. This can be made

faster via the following modification of MergeSort. Here, after the merge operation, only the first $k$ entries

are returned. This is faster than regular MergeSort, because we never need to merge arrays of length $>k.$

But what is the precise complexity?

Algorithm $1$: Modified MergeSort.

procedure SMALLEST$(A,k)$

if length of $Ak$ then

return MERGESORT $(A)$

else

left $=$SmaLLEST$\frac{A[1,\text{d}\text{o}\text{t}\text{s}\text{,}\frac{n}{2}],k}{\frac{?}{?}}$ the smallest $k$ entries of the left half

right $=$Smallest$\frac{A[\frac{n}{2}+1,\text{d}\text{o}\text{t}\text{s}\text{,}n],k}{\frac{?}{?}}$ the smallest $k$ entries of the right half

merged left, right