Question

The time complexity of quick sort algorithm which makes use of median

Answer 1

Explanation:

The worst case time complexity of a typical implementation of QuickSort is O(n2). ... The idea is bas.ed 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....

Answer 2

Quick sort is the sorting algorithm in which  divide and conquer is used as the most basic approach. The average complexity of time in quick sort is O(N log(N)).

Time complexity of Quick sort algorithm:

• Time complexity of an algorithm is the time consumed by a computer to run an algorithm.
• Quick sort algorithm create a partition of array around a element which is choose as pivot and we, for each partition same steps are going to repeat, until we get a sorted array.

The complexity of time is calculates as:

T(n) = Time Complexity of for input of size n in quick sort algorithm.

Now,

$T(n)=T(n) = T(I) + T(n-I) + M(n)$

where,  

T(I) = Time Complexity for input of size I.

T(n-I) = Time Complexity for input of size n-I.

M(n) = Time Complexity of searching the pivot element for n elements.

Algorithm      

used               Average              Best              worst

Quicksort $O(n*log(n))$          $O(n*log(n))$            $O(n^2)$