Expected depth of quicksort tree

Question

It's known that complexity of randomized quicksort algorithm can be estimated as $O(N\log N)$, where $N$ is the length of an array to be sorted. I know two different proofs of this estimation, where we assume that all elements are different, and a pivot is chosen randomly for each step. But these proofs estimate all complexity of the algorithm but not the depth of recursion calls tree. I want to prove that expected depth estimated as $O(\log N)$. This is my plan: let $\xi_N$ be the height of tree (random value), so $$E\xi_N=\frac{1}{N}\sum_{i=1}^{N}E\max(\xi_{i-1},\xi_{N-i})+1$$ But I can't compute this. Any ideas

Answer 1

You may prove the estimation $O(k^3)$ for $E(2^{\xi_{k}})$. Then, you can use the Jensen's inequality to show $2^{E(\xi_k)} \leq E(2^{\xi_{k}})$. Taking $log(\cdot)$ of both parts proves the result (Lecture notes with full details).