Show that randomized quick-sort runs in O(nlogn) time with probability

Show that randomized quick-sort runs in O(nlogn) time with probability at least 1−1/n, that is, with high probability, by answering the following:

a. For each input element x, define C_{i, j}(x) to be a 0/1 random variable that is 1 if and only if element x is in j+1 subproblems that have size s such that (3/4)ⁱ⁺¹n < s ≤ (3/4)ⁱn. Argue why we need not define C_{i, j} for j > n.

b. Let X_{i, j} be an independent 0/1 random variable that is 1 with probability 1/2^j, and let L=⌈log_4/3 n⌉. Argue that Σ^L−1_i=0 Σⁿ_j=0C_{i, j}(x) ≤ Σ^L−1_i=0 Σⁿ_j=0 X_{i, j}.

c. Show that the expected value of Σ^L−1_i=0 Σⁿ_j=0 X_{i, j} is (2−1/2n)L.

d. Show that the probability that Σ^L_i=0Σⁿ_j=0 X_{i, j} > 4L is at most 1/n², using the Chernoff bound that states that if X is the sum of a finite number of independent 0/1 random variables, having expected value μ > 0, then Pr(X > 2μ) < (4/e)^−μ, where e = 2.71828128. . ..

e. Argue that randomized quick-sort runs in O(nlogn) time with probability at least 1−1/n.

Contact Us

Enjoy 24/7 customer support for any queries or concerns you have.

Phone: +1 213 3772458

Email: support@gradeessays.com