Show that randomized quick-sort runs in O ( n log n ) time with probability at least 1−1/ n , that is, with high probability , by answering the following: a. For each input element x , define Ci , j (...

at least 1−1/n, that is, with

high probability
, by answering the following:

a. For each input element
x, define
Ci,
j(x) to be a 0/1 random variable

that is 1 if and only if element
x
is in
j+1 subproblems that belong

to size group
i. Argue why we need not define
Ci,
j
for
j
>
n.

b. Let
Xi,
j
be a 0/1 random variable that is 1 with probability 1/2j
,

independent of any other events, and let
L
= log4/3
n_. Argue why

Σ
<sup>L

−
1</sup>

<sub>i

=0</sub>
Σ
ⁿ
<sub>j

=0</sub>
Ci,
j(x) ≤ Σ
<sup>L

−
1</sup>

<sub>i

=0</sub>
Σ
ⁿ
<sub>j

=0</sub>
Xi,
j.

c. Show that the expected value of ΣL
^−
1

<sub>i

=0</sub>
Σ
ⁿ
<sub>j

=0</sub>
Xi,
j
is (2−1/2n)L.

d. Show that the probability that ΣLi

=0Σnj
=0Xi,
j
> 4L
is at most 1/n2,

using the

Chernoff bound

that states that if
X
is the sum of a finite

number of independent 0/1 random variables with expected value

μ
> 0, then Pr(X
> 2μ)
e)−μ, where
e
= 2.71828128. . ..

e. Argue why the previous claim proves randomized quick-sort runs in

O(nlog
n) time with probability at least 1−1/n.