$)$ Suppose you are given $k$ sorted non$-$empty lists $A_1,$dots,$A_k$

that consist of $n$ elements in total. Your task is to merge them into one

big sorted list. We will use the merge procedure described in class, which

can merge two lists into one in linear time, i$.$e$.,$ in $(n_1+n_2)$ time where

$n_1$ and $n_2$ are the sizes of the two input lists, respectively. You may

assume that $k$ is a power of $2.$

$($a$)(5$ points$)$ Consider the following simple iterative algorithm: First

merge $A_1$ and $A_2$ into one list, then merge the resulting list with $A_3,$

then $A_4,$dots,$A_k.$ Show that the $($worst$-$case$)$ running time of this

algorithm is $O(nk).$

$($b$)(2$ points$)$ Show that the $O(nk)$ running time is tight, i$.$e$.,$ its running

time is also $(nk),$ thus $(nk).$

$($c$)(2$ points$)$ What's the best$-$case running time of this iterative algo$-$

rithm? Explain.