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.