34.5 Exercises


  1. Which of the following function(s) have the slowest order of growth in terms of Big Theta?

  2. To solve puppy, cat, dog for 12 items, what is the theoretical minimum number of comparisons we have to make, based on the argument used in lecture? Please round your answer up to the nearest whole number.

  3. Which of the following statements are true?

Problem 1

In lecture, we proved that logN!Θ(NlogN)\log N! \in \Theta(N \log N). Thus, both NlogNN \log N and logN!\log N! have the same order of growth, and are slower than N2N^2 or N!logN!N! \log N!.

Problem 2

ceil(log212!)=29ceil(\log_2 12!) = 29, based on the equation we saw in lecture.

Problem 3


  1. Suppose we add a new method to Arrays.sort that takes in an array of strings. What algorithm should Arrays.sort(String[] x) use?

Problem 1

Quicksort. We don't need stability, since strings are only equal by .equals if they are exactly the same. Quicksort, then, is the best algorithm since it is empirically the fastest.

Last updated