retagged by
4,549 views

3 Answers

Best answer
47 votes
47 votes

The algorithm will take maximum time when:

  1. The array is already sorted in same order.(Here,ascending order)
  2. The array is already sorted in reverse order.
  3. All elements are same in the array(Here,we have n distinct elements).So, we can say the above points (1) and (2) as answers.
edited by
0 votes
0 votes
If the elements in the array are sorted(ascending/descending), quick sort takes O(n^2). and as the elements are distinct as mentioned in question, third case being if the elements are same doesn’t apply here. The above mentioned are worst cases for quick sort.
0 votes
0 votes

If it is unlikely that the data will be sorted, and you are willing to accept O(n^2) in the rare cases when the array is sorted then use the leftmost or rightmost element.

Related questions

39 votes
39 votes
5 answers
1
Kathleen asked Sep 12, 2014
16,516 views
Following algorithm(s) can be used to sort $n$ in the range $[1\ldots n^3]$ in $O(n)$ timeHeap sortQuick sortMerge sortRadix sort
7 votes
7 votes
4 answers
2
Kathleen asked Sep 12, 2014
3,031 views
Many of the advanced microprocessors prefetch instructions and store it in an instruction buffer to speed up processing. This speed up is achieved because ________
9 votes
9 votes
2 answers
3
Kathleen asked Sep 13, 2014
3,431 views
Start and stop bits do not contain any "information" but are used in serial communication forError detectionError correctionSynchronizationSlowing down the communications...
17 votes
17 votes
2 answers
4
Kathleen asked Sep 13, 2014
4,490 views
Mention the pass number for each of the following activities that occur in a two pass assembler:object code generationliterals added to literal tablelisting printedaddres...