Question

What are the best and worst case time complexities of quick sort?

Answer 1

Best: n log(n)

Worst: O(n^2)

Answer 2

Answer:

As you have enough knowledge of how Quick Sort works , like finding pivot,splitting the current array and again doing the same recursively for each sub arrays, it is easy to analyze time complexity with these things into consideration :

Best Case is when the pivot element divides the list into two equal halves by coming exactly in the middle position.

It’s time complexity is O(nlogn) .

Worst Case is when the list is either arranged in ascending or descending order.Then the time complexity increases to O(n^2).

Worst Case:

Worst case occurs when at each recursion we get next pivot to split arrays is at end of the array.

If N is the length of array and having current pivot at starting position of array,

pivot at last index is identified only traversing array from start to end . After fixing pivot and splitting resultant sub arrays of length are (N-1),1.

Again this (N-1) sub array finds next pivot at last index resulting array partitions with lengths (N-2),1.

This process repeats until the final sub arrays lengths are both 1,1.

So,this can be mathematically drawn into paper as

at step 1: with N elements , time complexity for this partition is

T(N)= N + T(N-1)

Where T(N-1) is time complexity of partition to be processed recursively and N is the time needed to compare N elements with a fixed pivot.

at step 2:with N-1 elements,

T(N-1)=(N-1) + T(N-2)

T(N-2) = (N-2) + T(N-3)

...

T(3) = 3 + T(2)

T(2) = 2 + T(1)

T(1) = 0 as time to partition array with length ‘1’ is 0 with no partitions

Hence,

T(N) = N + (N-1) + (N-2) ... + 3 + 2 ≈ N*(N+1)/2

= (N^2)/2

=O(N^2)

Explanation: