7-3

7-3 Alternative quicksort analysis
An alternative analysis of the running time of randomized quicksort focuses on the expected running time of each individual recursive call to RANDOMIZEDQUICKSORT, rather than on the number of comparisons performed.
a. Argue that, given an array of size n, the probability that any particular element is chosen as the pivot is 1/n. Use this to define indicator random variables Xi = I {i th smallest element is chosen as the pivot}. What is E[Xi] ? b. Let T .n/ be a random variable denoting the running time of quicksort on an array of size n. Argue that
$$E[T(n)] =E\Big[\sum_{q=1}^n X_q (T(q-1)+T(n-q)+\theta(n))\Big]$$ c. Show that we can rewrite equation (7.5) as
$$E[T(n)] = 2/n \sum_{q=2}^{n-1} E[T(q)]+\theta(n)$$ d. Show that
$$\sum_{k=2}^{n-1} k lg k \leq 1/2 n^2 lgn - 1/8 n^2$$ (Hint: Split the summation into two parts, one for k = 2,3,...,$\lceil n/2\rceil$-1 and one for $k = \lceil n/2\rceil,...,n-1.$)
e. Using the bound from equation (7.7), show that the recurrence in equation (7.6) has the solution E[T(n)] =\theta(n lg n). (Hint: Show, by substitution, that $E[T(n)] \leq an lg n$ for sufficiently large n and for some positive constant a.)
a. To choose an element from n elements we know the probability is 1/n. Since each element has a equal probability of getting picked.
if we define a random variable Xi = I {i th smallest element is chosen as the pivot}
But for the element to be ith smallest we need pick the element from n elements. we need consider this as well. so $E[X_i] = \sum_{j=1}^{n} Pr\{select an element j and j is ith smallest element\}$ the event mentioned above are independent. Hence for independent events $$A \cap B = A . B$$ $$E[X_i] = \sum_{j=1}^{n} Pr\{select an element j\} Pr\{j is ith smallest element\}$$ $$E[X_i] = \sum_{j=1}^{n} 1/n 1/n $$ $$E[X_i] = 1/n $$ b. The running time of quick sort on a array of size n is dependent on the size of sub-arrays. The subarray size is dependent of probability of picking a pivot element. We can sum size of subarrays resulting from all possible pivots multiplied by the probability of pivot. $$E[T(n)] = E \big[ \sum_{q=1}^n X_q (T(q-1)+T(n-q)+\theta(n)) \big]$$ we need add size subarray and $\theta (n)$ because it is the time taken for partitioning the array.
c. $$E(T(n)) = E \big[ \sum_{q=1}^n X_q (T(q-1)+T(n-q)+\theta(n)) \big]$$ using linearity of expectation $$E(T(n)) = \sum_{q=1}^n E[X_q] (T(q-1)+T(n-q)+\theta(n)) $$ since E[X_q] is 1/n from a. $$E(T(n)) = \sum_{q=1}^n 1/n (T(q-1)+T(n-q)+\theta(n)) $$ $$E(T(n)) = 1/n (\sum_{q=1}^n T(q-1)+ \sum_{q=1}^n T(n-q)+\sum_{q=1}^n \theta(n)) $$ $$E(T(n)) = 1/n (E[T(0)]+E[T(1)]+..E[T(n-1)]+E[T(n-1)]+..+E[T(1)]+E[T(0)]+ n .\theta(n)) $$ $$E(T(n)) = 1/n (E[T(2)]+..E[T(n-1)]+E[T(n-1)]+..+E[T(2)]+ n .\theta(n)) $$ since T(0) and T(1) is $\theta(1)$ $$E(T(n)) = 1/n ( 2(E[T(2)]+..E[T(n-1)])+ n .\theta(n)) $$ $$E(T(n)) = 1/n ( 2 \sum_{q=2}^{n-1} E[T(q)] )+ n. 1/n .\theta(n)) $$ $$E(T(n)) = 2/n \sum_{q=2}^{n-1} E[T(q)] + \theta(n)) $$ d. $$\sum_{k=2}^{n-1} k log k \leq 1/2 n ^2 lg n -1/8 n ^2$$ $$=\sum_{k=2}^{\lceil n/2 - 1 \rceil} k log k + \sum_{k= \lceil n/2 \rceil }^{n-1} k log k $$ $$\leq \sum_{k=2}^{\lceil n/2 - 1 \rceil} k log n/2 + \sum_{k= \lceil n/2 \rceil }^{n-1} k log n $$ $$\leq log n/2 \sum_{k=2}^{\lceil n/2 - 1 \rceil} k + log n \sum_{k= \lceil n/2 \rceil }^{n-1} k $$ $$= log \frac {n}{2}( \frac {(n/2-1).n/2 } {2} -1 )+ log n (\frac{n .(n-1)} {2} - \frac {(n/2-1).n/2 } {2}) $$ $$\leq log \frac {n}{2} \frac {(n/2).(n/2) } {2} + log n (\frac{n.n}{2} - \frac {(n/2).n/2 } {2}) $$ $$= log n \frac {(n^2)} {8} - log 2 \frac {(n^2)} {8} + log n \frac{\frac{n}{2} \frac{n}{2}}{2} - \frac {(n/2).n/2 } {2} $$ $$= log n \frac {(n^2)} {8} - \frac {(n^2)} {8} + log n \frac{ n^2}{2} - log n \frac {n^2} {8} $$ $$= - \frac {(n^2)} {8} + log n \frac{ n^2}{2} $$ e. $$E(T(n)) = 2/n \sum_{q=2}^{n-1} E[T(q)] + \theta(n)) $$ lets use substituion method and assume E[T(q)] = c q log q over q = 2 to n-1 $$E(T(n)) = 2/n \sum_{q=2}^{n-1} c q log q + \theta(n)) $$ from equation 7.7 $$E(T(n)) = 2/n c (log n \frac{ n^2}{2}- \frac {(n^2)} {8} ) + \theta(n)) $$ $$E(T(n)) = 2c (log n \frac{n}{2} - \frac {(n)} {8} ) + \theta(n)) $$ $$E(T(n)) = c n log n - c \frac {(n)} {4} ) + k n $$ $n \geq 4k$ $$E(T(n)) \leq c n log n $$