Question

The median of n elements can be found in O(n) time. Which one of the following is correct about the complexity of quick sort, in which remains is selected as pivot?

• A. $\Theta \left(n\right)$
• B. $\Theta \left(n^3\right)$
• C. $\Theta \left(n^2\right)$
• D. $\Theta$(n log n)

Answer 1

The correct option is D $\Theta$(n log n)

If the median of n elements can be found in 0(n) time and we select the median as pivot. Then quicksort sort n elements of an array A[1],...A[n] as follows. We permute the elements in the array so that for same j all the records with key less than v appear in A[1] ,...A[j] and all those with keys v or greater appear in A[j + 1] ,....A[n]. We then apply quicksort recursively to A[1],...,A[j] and to A[j + 1] ,...,A[n].
The recursion equation becomes for some valus of i
$T\left(n\right)\le \frac{1}{n}{\sum }_{i=i}^n\left(T\right(i-1)+T(n-1)$
The solution of the T(n)$\le \Theta$ ( n log n) Given to find median 0(n) time required.