edited by
6,174 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.

edited by

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

0 votes
0 votes
1 answer
2
Edwees asked Feb 6, 2017
1,890 views
We have a list of pairs [("Tariq",71),("Brinda",85),("Shweta",71),("Sunita",85),("Salma",72),("Uday",60)], where each pair consists of a student's name and his/her marks ...
0 votes
0 votes
1 answer
3
saurabh12345 asked Jul 24, 2018
400 views
Insertion sort uses an incremental approach for designing algorithm can someone please explain?
0 votes
0 votes
0 answers
4
Sajal Mallick asked Nov 27, 2023
171 views
As we have to select maximal set of “non overlapping” activities. So like job scheduling algo of greedy we can solve it. So according to that complexity must be O(n l...