Problem Set 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 time.)

  • \(n(\log n)^2\)
  • \(n\)
  • \(n\log n\)
  • \(n^2\log n\)

ANSWER: It follows that the height of the recursion tree is . Thus, overall running time is ; option 3 is correct.

You are given functions and such that . Is ? (Here is some positive constant.) You should assume that and are nondecreasing and always bigger than 1.

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

ANSWER: Let

Substituting the inequality by definition of Big-Oh, and the min value of

The expression is precisely the definition of Big-Oh; therefore, option 4 is correct.

Assume again two (positive) nondecreasing functions and such that . Is ? (Multiple answers may be correct, you should check all of those that apply.)

  • Yes if for all sufficiently large
  • Never
  • Sometimes yes, sometimes no (depending on the and )
  • Always

ANSWER:

Raising both sides to the power of 2, since and are positive increasing functions

The expression looks like it fits the bill for Big-Oh, but remember that expression holds only for some large enough . Therefore, option 1 is correct for all . For , we don’t really know, so option 3 is also correct.

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

  • \(\Theta(n\log k)\)
  • \(\Theta(n^2k)\)
  • \(\Theta(nk^2)\)
  • \(\Theta(nk)\)

ANSWER: Merging two sorted arrays with and elements, respectively, takes time. This strategy begins by merging two arrays of size to create an array of size . It then merges that with an array of size , and so on. Thus, the running time is

We can improve the running time by observing that the input is exactly the same as we see in the last level of the Merge Sort recursion tree (assuming the input array breaks up evenly into halves). Therefore, if we merge pairwise, we get the same running time as for Merge Sort, which is for an input array of size ; Since the total number of elements in the given problem is , we get .

Arrange the following functions in increasing order of growth rate (with following in your list if and only if .

  • \(n^2\log n\)
  • \(2^n\)
  • \(2^{2^n}\)
  • \(n^{\log n}\)
  • \(n^2\)

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->c->d->e (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).

ANSWER: eadbc (plot them).