> [!NOTE] Theorem > Let $n$ be a positive natural number and $A[1,2,\dots,n]$ an array. Let $Z$ denote the number of comparisons for [[Randomized Quicksort|randomized quicksort]] to sort $A.$ Then the [[Expectation of Discrete Real-Valued Random Variable|expectation]] of $Z$ satisfies $\mathbb{E}[Z]\leq 2n\log n.$ **Proof**: For all $i,j\in[n]$ with $i\neq j,$ let $R_{ij}$ denote the event that $A[i]$ and $A[j]$ are compared. Let $X_{ij}$ be the indicator function for $R_{ij}$ given by $X_{ij}=\begin{cases} 1 & \text{if }a_{i},a_{j} \text{ are compared} \\ 0 & \text{otherwise} \end{cases}$which is a discrete real-valued random variable. Then $Z=\sum_{i<j}X_{ij}.$ Equivalently, let $A^{*}= \{ a_{1}^{*},a_{2}^{*} ,\dots,a_{n}^{*} \}$ be the correctly sorted list. Denote a random variable $Y_{ij}$ with $i,j\in [n]$ as $Y_{ij}=\begin{cases} 1 & \text{if }a_{i}^{*},a_{j}^{*} \\ 0 & \text{otherwise} \end{cases}$then we have $Z=\sum_{i<j}Y_{ij}.$ For $a_{i}^{*}$ and $a_{j}^{*}$ we must ensure that either $a_{i}^{*}$ or $a_{j}^{*}$ is a pivot and that we do not choose any of $\{ a_{i+1}^{*}, \dots,a_{j-1}^{*} \}$ (otherwise, $a_{i}^{*}$ and $a_{j}^{* }$ will be split into different sets and will never be compared). That means, we are doing a dart game over $\{a_{i}^{*}, a_{i+1}^{*}, \dots,a_{j-1}^{*}, a_{j}^{*}\}$ (if beyond this set, we throw another dart): we throw a dart at random into the array. If we hit $a_{i}^{*}$ or $a_{j}^{*}$, then $Y_{ij}=1$ otherwise $Y_{ij}=0.$ Thus $\mathbb{P}(Y_{ij})= \frac{2}{j-1+1}$By linearity of expectation, $\begin{align} \mathbb{E}[Z] &=\sum_{i<j}\mathbb{E}[Y_{ij}] \\ &= 2\sum _{i=1}^{n-1} \sum_{j=i+1}^{n} \frac{1}{j-i+1} \\ &= 2\sum_{i=1}^{n-1} \frac{n-i}{i+1} \\ &= 2\sum_{k=2}^{n} \frac{n}{k} - 2 \sum_{i=1}^{n-1} \frac{i}{i+1} \\ &= 2\left( \sum_{k=1}^{n} \frac{n}{k} - \frac{n-1}{2} \right) \\ &\leq 2 n \log n \end{align}$using [[Approximation of Harmonic Numbers]]. **Proof**: Let $C_{n}$ be the be the number of comparisons needed by randomized quicksort to sort an array of length $n.$ Then $C_{n}$ is a [[Discrete random variables|DRV]]. Let $A$ be an array of length $n.$ Let $B_{j}$ be the event that we choose the $j$th smallest value of $A$ as the pivot. Then $\mathbb{P}(B_{j})=\frac{1}{n}.$ The procedure takes $n-1$ comparisons to split $A$ into the set of $A_{\text{left}}^{j}$ values smaller than the pivot which has size $j-1$ and the set $A_{\text{right}}^{j}$ of values bigger than or equal to the pivot which has length $n-j.$ Therefore given the event $B_{j},$ the number of comparisons needed is $n-1+C_{j-1}+C_{n-j}.$ By [[Total Expectation Theorem]], $\begin{align} M_{n}&:=\mathbb{E}[C_{n}]=\sum_{j=1}^{n}\mathbb{E}(C_{n}\mid B_{j})\mathbb{P}(B_{j}) \\ &= \sum_{j=1}^{n} (n-1+M_{j-1}+M_{n-j}) \frac{1}{n} \\ &= n-1 + \frac{2}{n} \sum_{j=1}^{n-1}M_{j} \\ &= \mathcal{O}(n\log n) \end{align}$