# Divide and Conquer, Sorting and Searching, and Randomized Algorithms Week 1 | Problem Set #1 Quiz Answer

## Divide and Conquer, Sorting and Searching, and Randomized Algorithms Week 1 | Problem Set #1 Quiz Answer

#### Problem Set #1

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

**Write your 5-letter answer, i.e., the sequence in lower case letters in the space provided. For example, if you feel that the answer is a->b->->d-> (from smallest to largest), then type abcde in the space provided without any spaces before / after / in between the string.**

**You can assume that all logarithms are base 2 (though it actually doesn’t matter).**

*WARNING: this question has multiple versions, you might see different ones on different attempts!*

*dcbae Please note: Each of the following will be interpreted as a single variable, not as a product of variables: dcbae. To multiply variables, please use * (e.g. enter x*y to multiply variables x and y).*

- dcbae