3-way-Merge Sort : Suppose that instead of dividing in half at each step of Merge Sort, you divide into thirds, sort each third, and finally combine all of them using a three-way merge subroutine. What is the overall asymptotic running time of this algorithm? (Hint: Note that the merge step can still be implemented in $O(n)$ time.)

You are given functions $f$ and $g$ such that $f(n)=O(g(n))$. Is $f(n)*log_2(f(n)^c) = O(g(n)*log_2(g(n)))$ ? (Here $c$ is some positive constant.) You should assume that $f$ and $g$ are nondecreasing and always bigger than 1.

Assume again two (positive) nondecreasing functions $f$ and $g$ such that $f(n)=O(g(n))$. Is $2^{f(n)}=O(2^{g(n)})$ ? (Multiple answers may be correct, you should check all of those that apply.)

k-way-Merge Sort. Suppose you are given $k$ sorted arrays, each with $n$ elements, and you want to combine them into a single array of $kn$ elements. Consider the following approach. Using the merge subroutine taught in lecture, you merge the first 2 arrays, then merge the $3^{rd}$ given array with this merged version of the first two arrays, then merge the $4^{th}$ given array with the merged version of the first three arrays, and so on until you merge in the final ($k^{th}$) input array. What is the running time taken by this successive merging algorithm, as a function of $k$ and $n$? (Optional: can you think of a faster way to do the k-way merge procedure ?)