retagged by
15,133 views
2 votes
2 votes

The running time of Quick sort algorithm depends heavily on the selection of:

  1. No. of inputs
  2. Arrangement of elements in an array
  3. Size of elements
  4. Pivot Element
retagged by

4 Answers

3 votes
3 votes
D is correct.

If we select the median and pivot expected worst case running time is O(n log n) While in general worst case is $O(n^2)$
0 votes
0 votes

The worst case time complexity of a typical implementation of Quick Sort is $O(n^{2})$. The worst case occurs when the picked pivot is always an extreme (smallest or largest) element. This happens when input array is sorted or reverse sorted and either first or last element is picked as pivot.

Although randomized Quick Sort works well even when the array is sorted, there is still possibility that the randomly picked element is always an extreme.

Can the worst case be reduced to $O(nLog_{2}n)$?

The answer is yes, we can achieve $O(nLog_{2}n)$ worst case. The idea is based on the fact that the median element of an unsorted array can be found in linear time. So we find the median first, then partition the array around the median element.

 Running time of Quick sort algorithm depends heavily on the selection of Pivot Element

0 votes
0 votes
option D) According to the question Pivot element should be the answer .
0 votes
0 votes
(D) The running time of quick sort depends on an arrangement of elements in an array. If an array is sorted, then it gives worst-case time complexity i.e., O(n2 )
Answer:

Related questions

2 votes
2 votes
2 answers
1
admin asked Mar 31, 2020
8,491 views
The Knapsack problem belongs to which domain of problems?OptimizationNP completeLinear SolutionSorting
4 votes
4 votes
4 answers
2
admin asked Mar 31, 2020
84,217 views
Two main measures for the efficiency of an algorithm are:Processor and MemoryComplexity and CapacityTime and SpaceData and Space
1 votes
1 votes
1 answer
3
admin asked Mar 31, 2020
1,068 views
What is the solution to the recurrence $T(n)=T \bigg (\dfrac{n}{2} \bigg )+n$?$O(\log n)$$O(n)$$O(n\log n)$None of these
0 votes
0 votes
2 answers
4