Which of the following statements is not true?
1.For every fixed strategy to choose a pivot for quicksort, we can construct a worst case input that requires time O(n2).
2.If we randomly choose a pivot element each time, quicksort will always terminate in time O(n log n).
3. If we could find the median in time O(n), quicksort would have worst case complexity O(n log n).
4.Quicksort and merge sort are both examples of divide and conquer algorithms.
B: FALSE: Suppose, when we make random choices, we cannot rule out the worst case behaviour, which is O(n2).
Worst case possibilities are mainly two
All elements are having the same number.
If elements are in sorted order.