Introduction
In this assignment you are asked to mimic the analysis of randomized quicksort we covered in class in order to partially analyze randomized selection.
The following randomized select algorithm omits the while
loop of
the version we analysed in class.
def select2(A, p, q, i): n = q - p + 1 if n==1: return A[p] loc = randrange(p,q) # choose random integer in [p,q) r = partition(A,p,q,loc) # See quicksort slides k = r - p if (k == i): return A[r] if (i < k): return select2(A,p,r-1,i) else: return select2(A,r+1,q,i-k-1)
Consider the following recurrence for the running time of select2
.
There exist constants \(c, n_0>0\) such that \(\forall n\geq n_0\):
where
\begin{equation} \label{org7b0f3bb} X_j = \begin{cases} 1 & \text{if $r=j+p-1$}\\ 0 & \text{otherwise} \end{cases} \end{equation}1. Indicator variables
Prove the expected value \(E[ X_j ] = 1/n\). What assumptions do you need to make?
2. Expectation
Prove that
\begin{equation} \label{orgc24d40e} E[T(n)] ≤ (1/n) \sum_{j=1}^n E[\max(T(j-1), T(n-j))] + O(n) \end{equation}3. Eliminating max
Under the assumption that \(T(n)\) is strictly monotone increasing, i.e. that \(i>j\) implies \(T(i) > T(j)\) show that \eqref{orgc24d40e} implies
\begin{equation} \label{org5c06681} E[T(n)] ≤ (2/n) \sum_{j=\lfloor n/2 \rfloor}^{n-1} E[T(j)] + O(n) \end{equation}4. Discuss Assumptions
Why is assuming that the random variable \(T(n)\) is strictly monotone increasing stronger than with a deterministic recurrence?