GO Classes 2023 | IIITH Mock Test 1 | Question: 8

Answer 1

If the median value gets picked as the pivot, the array will be in sorted order after only a single pivot. If the smallest or largest gets picked, we're not quite done.

Probability of choosing median $= 1/3$ since there are just three types of values in equal proportion.

Answer 2

We know that quick sort will give best time complexity when partition will divide there array in two equal parts every time.ie, when every time pivot element selected will be the median of the array(sorted).

 

NOTE:- BUT FOR THAT WE HAVE TO PRIOR ONLY KNOW ABOUT THE ELEMENTS WHICH IS NOT ALWAYS POSSIBLE.

 

THEREFORE, of that will happen then:-T(n) equals 2T(n/2) + (n+1).    Which is like the merge sort therefore time complexity equals. N log N.

 

Note:-in this question this concept does not required to be applied so as such😁

 

 

But here in this question we know about the elements. So if we select the median element 1st time then after the 1st iteration only the elements will be sorted.

Therefore, probability equals (n/3) by n ,equals 1/3.