# Tag Info

According to Lemma 7.1 in these notes, if you construct a random BST on $\{0,\ldots,n-1\}$, then the expected depth of $x \in \{0,\ldots,n-1\}$ is $H_{x+1} + H_{n-x} - 2$, where $H_m$ is the $m$'th harmonic number. Summing over all $x$, the expected sum of depths is  \sum_{x=0}^{n-1} (H_{x+1} + H_{n-x} - 2) = 2 \sum_{i=1}^n (H_i - 1) = 2 \sum_{i=1}^n \sum_{...