The best-case analysis of QuickSort is achieved when the pivot is exactly the of the data to be sorted. In this case, the run time complexity of QuickSort is On the other hand, if the pivot is exactly the QuickSort has the worst-case complexity . If assuming each partition equally likely happens, then the average-case complexity is 1 point We learned some sorting algorithms require better than O(Nlog(N)) time complexity, such as Bucket sort achieving average-case time complexity (N), so the information theoretic lower bound O(Nlog(N)) for comparison-based sorting algorithms is useless in practice. True False 1 point Decision tree can be used to prove the lower bound complexity for general comparison-based sorting algorithms. Which of the following statements is FALSE regarding this analysis of the lower bound? InsertionSort should never be used in practice, because its worse-case complexity is O(N2) and it is suboptimal The number of leaf nodes in the decision tree is N !, where N is the number of data to be sorted Each leaf in the decision tree represents an ordering of N data items, and there are N ! different orderings of N elements. Stirling approximation is used to approximate N! by (N/e)N