Desempenho esperado de Rand-Select
[Enunciado]
Considere a recorrência
\[
E(n) =
n-1 +
\frac{2}{n}\,\sum_{i=\lfloor{n/2}\rfloor}^{n-1} E(i)\:.
\]
Fato 1:
Se $E(1) = 0$ então
$E(n) \leq 8\,n$
para $n = 1, 2, 3, 4, \dots$
Prova, por indução em $n\text{:}$
É fácil verificar que $E(2) = 1 \leq 8\cdot 2\text{.}$
Agora tome $n > 2$
e suponha que $E(i) \leq 8\,i$
para $i = 1, 2$
(esta é a hipótese de indução).
Então
\begin{eqnarray*}
E(n)
&\leq & n-1 +
\frac{2}{n}\:\sum\nolimits_{i=\lfloor{n/2}\rfloor}^{n-1} 8i\\
&\ = \ & n-1 +
\frac{2}{n}\:\Big(\sum\nolimits_{i=1}^{n-1} 8i \
- \sum\nolimits_{i=1}^{\lfloor{n/2}\rfloor-1} 8i\Big)\\
& = & n-1 +
\frac{8}{n}\:\Big(n(n-1)
- (\lfloor{\frac{n}{2}}\rfloor-1)\lfloor{\frac{n}{2}}\rfloor\Big)\\
& \leq & n-1 +
\frac{8}{n}\:\big(n(n-1)
- (\frac{n}{2}-2)(\frac{n}{2}-1)\big)\\
& = & n-1 +
\frac{8}{n}\:\big(n^2 - n - \frac{n^2}{4} + \frac{3n}{2} - 2\big)\\
& < & n-1 +
\frac{8}{n}\:\big(n^2 - n - \frac{n^2}{4} + \frac{3n}{2}\big)\\
& = & n-1 +
\frac{8}{n}\:\big(\frac{3n^2}{4} + \frac{n}{2}\big)\\
& = & n-1 + 6n + 4\\
& = & 7n + 3\\
& \leq & 7n + n\\
& = & 8n\,.
\end{eqnarray*}
Fato 2:
$E(n) \geq 2\,n$
para $n = 9, 10, 11 \dots$