Randomized Quicksort Analysis: Expected Running Time and Complexity

(a) To derive E(Xi), we need to consider the probability that the ith smallest number in the array is chosen as the pivot.

Since the pivot is chosen uniformly at random from the array, the probability of choosing the ith smallest number as the pivot is 1/n (assuming there are no duplicate numbers in the array).

Therefore, E(Xi) = 1/n.

(b) To prove that 2·(T(-1)+T(1)+...+T(n)) = E[T(n)], we need to consider the expected running time of randomized quicksort.

The running time of randomized quicksort on an array of size n can be divided into two parts: the time spent on partitioning the array and the time spent on recursively sorting the subarrays.

Let's consider the partitioning time first. The partitioning time is proportional to the size of the array being partitioned, which is n. Therefore, the expected partitioning time can be represented as n·E[Xi], where E[Xi] is the expected value of choosing the ith smallest number as the pivot.

Now let's consider the recursive sorting time. The recursive sorting time can be represented as the sum of the expected running times of sorting the subarrays. Since the size of the subarrays is smaller than n, we can represent the expected running time of sorting the subarrays as E[T(n')], where n' is the size of the subarray.

Therefore, the expected running time of randomized quicksort can be represented as:

E[T(n)] = n·E[Xi] + ∑ E[T(n')] = n·E[Xi] + ∑ E[T(n')] (1)

Now, let's consider the term ∑ E[T(n')]. We can rewrite it as:

∑ E[T(n')] = E[T(0)] + E[T(1)] + ... + E[T(n-1)] (2)

Comparing equation (1) with equation (2), we can see that the term ∑ E[T(n')] in equation (1) is equal to the term E[T(-1)] + E[T(0)] + E[T(1)] + ... + E[T(n-1)] in equation (2).

Therefore, we can rewrite equation (1) as:

E[T(n)] = n·E[Xi] + E[T(-1)] + E[T(0)] + E[T(1)] + ... + E[T(n-1)]

Since E[Xi] = 1/n (from part (a)), we can simplify the equation as:

E[T(n)] = E[T(-1)] + E[T(0)] + E[T(1)] + ... + E[T(n-1)] + (n)

The expected running time of quicksort on an array of size n can be represented as the sum of the expected running times of sorting the subarrays plus the time spent on partitioning the array.

The time spent on partitioning the array is proportional to the size of the array being partitioned, which is n. Therefore, the expected partitioning time can be represented as n.

The expected running time of sorting the subarrays can be represented as E[T(1)], as the size of the subarrays is 1.

Therefore, we can represent the expected running time of quicksort on an array of size n as:

E[T(n)] = E[T(1)] + (n)

(d) To prove that -k log k < n log n - n %, we need to consider the expected running time of quicksort on an array of size n.

Let's consider the case when k = 2, 3, ..., (n/2) - 1. In this case, we have two subarrays of size k and n-k. The expected running time of quicksort on these subarrays can be represented as E[T(k)] + E[T(n-k)].

Using part (c), we know that E[T(k)] = E[T(1)] + (k) and E[T(n-k)] = E[T(1)] + (n-k).

Therefore, the expected running time of quicksort on an array of size n when k = 2, 3, ..., (n/2) - 1 can be represented as:

E[T(n)] = E[T(1)] + (k) + E[T(1)] + (n-k) = 2E[T(1)] + (n)

Now let's consider the case when k = n/2, n/2+1, ..., n-1. In this case, we have two subarrays of size n-k and k. The expected running time of quicksort on these subarrays can be represented as E[T(n-k)] + E[T(k)].

Using part (c), we know that E[T(n-k)] = E[T(1)] + (n-k) and E[T(k)] = E[T(1)] + (k).

Therefore, the expected running time of quicksort on an array of size n when k = n/2, n/2+1, ..., n-1 can be represented as:

E[T(n)] = E[T(1)] + (n-k) + E[T(1)] + (k) = 2E[T(1)] + (n)

Since -k log k < 2E[T(1)] + (n) for k = 2, 3, ..., (n/2) - 1 and k = n/2, n/2+1, ..., n-1, we can conclude that:

-k log k < n log n - n %

(e) To show that the recurrence in (c) yields E[T(n)] = O(n log n), we need to use substitution to show that E[T(n)] < cn log n for some positive constant c when n is sufficiently large.

From part (c), we know that E[T(n)] = E[T(1)] + (n).

Let's assume that E[T(1)] = c' for some positive constant c'.

Therefore, we can rewrite the recurrence as:

E[T(n)] = c' + (n)

Now let's assume that E[T(n)] < cn log n for some positive constant c when n is sufficiently large.

Substituting this assumption into the recurrence, we have:

cn log n > c' + (n)

Simplifying the inequality, we get:

cn log n - n > c'

Since cn log n - n is an increasing function when n is sufficiently large, we can choose a constant c' such that cn log n - n > c' for n sufficiently large.

Therefore, we can conclude that E[T(n)] = O(n log n).

Randomized Quicksort Analysis: Expected Running Time and Complexity