Comment on page
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?
- The optimal sorting algorithm takes at mosttime.
- It is impossible to find a comparison-based sorting algorithm that takes less thancomparisons.
- It is impossible to find a comparison-based sorting algorithm that takes less thantime.
- It is impossible to find a sorting algorithm that takes less thantime.
- The optimal sorting algorithm takes at mosttime. We know of several sorts (for example, mergesort) that taketime 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 thancomparisons. This is the comparison sorting bound proved in lecture.
- It is impossible to find a comparison-based sorting algorithm that takes less thantime. 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 thantime. 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 shouldArrays.sort(String[] x)
use?
Last modified 7mo ago