in Algorithms edited by
4,623 views
0 votes
0 votes

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.

in Algorithms edited by
by
4.6k views

2 Comments

is it option A?
0
0
2 ) if we choose pivot randomly it increases the chance to get o(nlogn) but not always true
0
0

2 Answers

0 votes
0 votes
b ,c, d options are true for quicksort.

option a is correct.
0 votes
0 votes

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

  1. All elements are having the same number.

  2. If elements are in sorted order. 

Answer:

Related questions