Consider Quick sort algorithm used to sort an array of n distinct randomly ordered element. In every call the pivot is chosen as the first element of the current subarray. Let T(n) denote the expected time to sort the array. Assume that the time to partition is linear in the size of current subarray. Which of the following option represents T(n) in this scenario.

The correct option is:
$$T\left(n\right)=\frac{1}{n}\sum _{K=0}^{n-1}\left[T\right(K)+T(n-K-1\left)\right]+O\left(n\right)$$

Step-by-step Explanation:

1. Understanding Quick Sort Partitioning:
In the Quick sort algorithm, we choose a pivot element to partition the subarray of size n. Here, the pivot is chosen as the first element of the current subarray. Since the array contains n distinct elements that are randomly ordered, the chosen pivot is equally likely to end up in any of the sorted positions from index 0 to index n - 1. Specifically, the pivot will partition the array into two subarrays: one of size K (representing elements smaller than the pivot) and one of size n - K - 1 (representing elements larger than the pivot), where K can range from 0 to n - 1 with equal probability.

2. Probability of Pivot Position:
Since the input elements are randomly ordered, each possible size of the left subarray, K (where 0 ≤ K ≤ n - 1), occurs with equal probability:
$$P\left(\text{left subarray size is}K\right)=\frac{1}{n}$$

3. Formulating the Recurrence Relation for Expected Time:
For a fixed partition index K, the time taken to sort the subarray is the sum of:
- The time to sort the left subarray of size K, which is T(K)
- The time to sort the right subarray of size n - K - 1, which is T(n - K - 1)
- The linear time required to perform the partitioning, denoted as O(n)

To find the expected time T(n), we take the weighted average over all possible values of K from 0 to n - 1:
$$T\left(n\right)=\sum _{K=0}^{n-1}\frac{1}{n}\left[T\right(K)+T(n-K-1\left)\right]+O\left(n\right)$$

Factoring out the constant probability factor $\frac{1}{n}$ gives the final expected recurrence relation:
$$T\left(n\right)=\frac{1}{n}\sum _{K=0}^{n-1}\left[T\right(K)+T(n-K-1\left)\right]+O\left(n\right)$$