Question

What is the running time of Quicksort when the input array is sorted in ascending order? (please explain in detail)

Answer 1

Analysis of Time complexity of quick sort algorithm:

T(n) = T(k) + T(n-k-1) + (n)

Where k is the number of items less than pivot
n is number of items in array

The first two terms are included for the recursive quicksort calls.

The last term is for the partition algorithm used in quick sort.

Solution:

When the elements are already in sorted order, the smallest element is present at the start of array and the largest element is present at the end of array.

The worst case in the quick sort occurs when the algorithm selects the smallest or largest item as pivot.

The last element here is the largest element.

So, the worst case occurs when the array is already sorted.

The worst case time is computed as shown below.

T(n) = T(0) + T(n-0-1) + (n)

= T(n-1) + (n)

= ()

Therefore,  the running time of Quicksort when the input array is sorted in ascending order is  ().