Question

In QuickSort algorithm, which of the following statements is NOT true regarding the partition process?

a) Partition always divides the array into two non-empty subsets.

b) The element chosen as the pivot does not have to be the median of the array for the algorithm to be efficient.

c) After the partition, the pivot is in its final sorted position.

d) If the array is already sorted, partitioning can be done in O(1) time complexity.

Answer 1

Option D is correct,

Bcoz If quick sort is sorted then worst case is O(n^2), so its is not done inO(1)

Answer 2

Option D is correct 

T(n) = T(n-1) + T(n-k-1) + Cn  ...(This is recurrence relation of TC of quick sort)

therefore , worst case occurs when array is sorted , so the resulting partitions will have sizes of 0 and n-1 in each recursive call.

This leads to a recurrence relation where one partition has a size of 0, and the other partition has a size of n-1:

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

       = O(n^2)