Advanced Algorithm Q.29
0. Which of the following statements are true?
- A
R and QS returns the sorted list after O(n log n) comparisons on all inputs
- B
R and QS never returns an unsorted list on any input.
- C
For every input, there exist a random choice of pivots for which the algorithm makes O(n2) comparisons.
- D
For every input, most of the random choices of pivots result in the algorithm making O(n log n) comparisons.
