Comment on page

# 34.5 Exercises

- 1.Which of the following function(s) have the slowest order of growth in terms of Big Theta?
- $N \log N$
- $\log N!$
- $N^2$
- $N! \log N!$

- 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?
- The optimal sorting algorithm takes at most$\Theta(N \log N)$time.
- It is impossible to find a comparison-based sorting algorithm that takes less than$\Theta(N \log N)$comparisons.
- It is impossible to find a comparison-based sorting algorithm that takes less than$\Theta(N \log N)$time.
- It is impossible to find a sorting algorithm that takes less than$\Theta(N \log N)$time.

**The optimal sorting algorithm takes at most**$\Theta(N \log N)$**time**. We know of several sorts (for example, mergesort) that take$\Theta(N \log N)$time in the worst case. So the hypothetical "best" sorting algorithm cannot be worse than this.**It is impossible to find a comparison-based sorting algorithm that takes less than**$\Theta(N \log N)$**comparisons.**This is the comparison sorting bound proved in lecture.**It is impossible to find a comparison-based sorting algorithm that takes less than**$\Theta(N \log N)$**time**. Each comparison must take at least constant time, so the time complexity of comparison-based sorts has the same lower bound as the number of comparisons.**It is impossible to find a sorting algorithm that takes less than**$\Theta(N \log N)$**time.**The lower bound proved in lecture only applies to comparison-based sorts. We will see in future lectures how to use non-comparison sorts to reduce this runtime even further.

- 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?

Last modified 7mo ago