worst case in quck sort

Question

Consider a scenario of modified quick sort, where we have given an input sorted array A[1 . . . n], all elements of array are distinct and n ≥ 3. Pivot is the median of set of 3 elements [First element, middle element, and last element]. What will be worst case time complexity of modified quick sort?

• Ο(n2)
• Ο(n logn)
• Ο(n2 logn)
• Ο(n log log n)

I think it will be B but they have given as A....???

Comments

yes, your oslution is right but there is a confusion in the last line of the question. if middle element need to be pivot,. then why it is not directly given in the question. what is the source of question?

---

Clearly, the question says pivot is median of n elements, they have taken n=3 for explaining purpose

---

yes, but answer is O(n^2)  thats why confusion arise

thats why i want source of question

Answer 1

The correct answer is B.

Median of 'n' elements in a sorted array is the n/2 ^th element which falls exactly at the n/2 ^th position. Thus, dividing the array approximately in two equal halves.

Since, no complexity is given to find the median we will consider constant time.
Now, The recursive equation for this problem becomes:

$T(n) =O(1) + O(n) + T(n/2) + T(n/2)$

where O(1) is the complexity to find median in every recursive call.

Solve using Recursive tree method or Master's Theorem  : $O(nlogn)$

:)

Comments

See, Worst Case in Quick Sort arises on how we choose the Pivot element when:

1) If Array is already sorted in same order or reverse order, and pivot is chosen as first or last element, partitioning contain (n-1) elements at every level and the cost of partitioning at each level is O(n). Then Total Time Complexity becomes O(n²).

2) All elements are same, then choosing any element as pivot will make the time complexity again as O(n²).

Other than that, Quick Sort will give the best case = average case, where there is some ratio of n elements that are split during partitioning at every level, making the complexity O(nlogn).

:)

---

"Other than that, Quick Sort will give the best case = average case, where there is some ratio of n elements that are split during partitioning at every level, making the complexity O(nlogn)"

As you said yes it is true for best case = average case = WORST CASE and will be O(nlogn) and Also in the question they specifically mentioned to Calculate for WORST case.

---

Yes, for the above question, Worst case = Best case = Average case ;)