Question 1) 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.)

• n(log(n))2
• n2 log(n) 
• п 
• n log(n)

Question 2) You are given functions f and g such that f(n) = O(g(n)). Is f(n) * log2(f(n)) = O(g(n) * log2(g(n))) ? (Here cis some positive constant.) You should assume that f and g are nondecreasing and always bigger than 1.

• Sometimes yes, sometimes no, depending on the functions f and g
• Sometimes yes, sometimes no, depending on the constant c
• False
• True

Question 3) Assume again two (positive) nondecreasing functions f and g such that f(n) = O(g(n)). Is 27(n) = O(29(n)) ? (Multiple answers may be correct, you should check all of those that apply.)

• Always
• Yes if f(n) ≤ g(n) for all sufficiently large n
• Never
• Sometimes yes, sometimes no (depending on f and g)

Question 4) 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 3rd given array with this merged version of the first two arrays, then merge the 4th given array with the merged version of the first three arrays, and so on until you merge in the final (kth) 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 ?)

• θ(nk)
• θ(n2 k) 
• θ(nk2 )
• θ(n log(k))

Question 5) Arrange the following functions in increasing order of growth rate (with g(n) following f(n) in your list if and only if f(n) = O(g(n)))

• a)22 n
• b)2 n2
• c)n2 log(n)
• d)n
• e)n2 n

• dcbae