$$Na formula acima, ##F[n]## e o numero medio de comparacoes para um vetor de tamanho ##n##, e ##F[k,n]## e o numero medio de comparacoes para o vetor de tamanho ##n##, no caso em que o corte foi feito no elemento ##k##.Vamos calcular ##F[k,n]## agora. Esse valor depende de onde esta o numero que estamos procurando. Eu nao sei onde esta o numero; como estamos calculando o caso medio, precisamos tirar a media sobre todos as posicoes possiveis.$$F[k,n]=\sum_{0\le i\lt n}\frac{1}{n}F[i,k,n]=\frac{1}{n}\sum_{0\le i\lt n}F[i,k,n]$$Agora ##F[i,k,n]## significa o valor medio para um vetor de tamanho ##n##, cortado na posicao ##k##, e com numero final na posicao ##i##. Nos temos tres casos agora. Se ##i=k##, entao voce so precisa comparar uma vez, a comparacao vai ser verdadeira e o algoritmo termina. Se ##i\lt k##, entao voce compara uma vez e faz recursao para o lado esquerdo. Se ##i\gt k##, entao voce compara uma vez e faz recursao para o lado direito. Resumindo:$$F[i,k,n]=\begin{cases}1+F[k] &(i \lt k) \\1 &(i = k) \\1+F[n-k-1] &(i \gt k) \\\end{cases}$$Podemos sintetizar tudo que vimos em uma unica recorrencia.$$\begin{align*}F[0] &= 0 \\F[n] &= \frac{1}{n} \sum_{0\le k \lt n}\left( \frac{1}{n}\sum_{0\le i\lt k}\left(1+ F[k]\right) + \frac{1}{n} + \frac{1}{n}\sum_{k\lt i\lt n}\left(1+ F[n-k-1]\right)\right) \end{align*}$$Agora e so resolver!Antes de mais nada, vamos coletar quem e constante em relacao ao indice da somatoria. Todos os ##1/n## coletam, e as somatorias mais internas viram constantes.$$\begin{align*}F[n] &= \frac{1}{n^2} \sum_{0\le k \lt n}\left( \sum_{0\le i\lt k}\left(1+ F[k]\right) + 1 + \sum_{k\lt i\lt n}\left(1+ F[n-k-1]\right)\right) \\&= \frac{1}{n^2} \sum_{0\le k \lt n} k \left(1+ F[k]\right) + 1 + \left(n-k-1\right)\left(1+ F[n-k-1]\right)\\&= \frac{1}{n^2} \sum_{0\le k \lt n} k + k F[k] + 1 + n-k-1 +\left(n-k-1\right)F[n-k-1]\\&= \frac{1}{n^2} \sum_{0\le k \lt n} n + k F[k] +\left(n-k-1\right)F[n-k-1]\\&= 1+\frac{1}{n^2} \left(\sum_{0\le k \lt n} k F[k] +\sum_{0\le k \lt n} \left(n-k-1\right)F[n-k-1] \right)\\\end{align*}$$Vamos focar naquela segunda somatoria. Primeiro fazemos ##q=n-k-1##:$$\sum_{0\le k \lt n} \left(n-k-1\right)F[n-k-1] =\sum_{0\le n-q-1 \lt n} qF[q] $$Agora e so manipular os indices:$$\begin{align*} 0\le n-&q-1 \lt n \\ 1-n\le -&q \lt 1 \\ -1\lt &q \le n-1 \\ 0\le &q \lt n \\\end{align*}$$Olha so, a segunda somatoria e igual a primeira!$$ \sum_{0\le n-q-1 \lt n} qF[q] =\sum_{0\le q \lt n} qF[q] =\sum_{0\le k \lt n} kF[k] $$Substituindo, chegamos em uma formula curta para ##F[n]##:$$\begin{align*}F[n] &= 1+\frac{1}{n^2} \left(\sum_{0\le k \lt n} k F[k] +\sum_{0\le k \lt n} \left(n-k-1\right)F[n-k-1] \right) \\&= 1+\frac{1}{n^2} \left(\sum_{0\le k \lt n} k F[k] +\sum_{0\le k \lt n} kF[k] \right) \\&= 1+\frac{2}{n^2} \sum_{0\le k \lt n} k F[k] \\\end{align*}$$A somatoria ainda esta atrapalhando, o ideal seria sumir com ela. Uma maneira de fazer isso e isolando:$$\begin{align*}F[n] &= 1+\frac{2}{n^2} \sum_{0\le k \lt n} k F[k] \\\sum_{0\le k \lt n} k F[k] &= \frac{n^2}{2}\left(F[n]-1\right)\end{align*}$$Essa ultima formula vale para todo ##n##, em especial vale tambem para ##n-1##:$$\begin{align*}\sum_{0\le k \lt n} k F[k] &= \frac{n^2}{2}\left(F[n]-1\right) \\\sum_{0\le k \lt n-1} k F[k] &= \frac{(n-1)^2}{2}\left(F[n-1]-1\right) \\\end{align*}$$Aha! Agora e so subtrair uma da outra que a somatoria desaparece!$$\begin{align*}\sum_{0\le k \lt n} k F[k] - \sum_{0\le k \lt n-1} k F[k] &= \frac{n^2}{2}\left(F[n]-1\right) - \frac{(n-1)^2}{2}\left(F[n-1]-1\right)\\(n-1) F[n-1] &= \frac{n^2}{2}\left(F[n]-1\right) - \frac{(n-1)^2}{2}\left(F[n-1]-1\right)\\(n-1) F[n-1] &= \frac{n^2}{2}F[n]-\frac{n^2}{2} - \frac{(n-1)^2}{2}F[n-1]+\frac{(n-1)^2}{2}\\\frac{n^2}{2}F[n] &= \left(\frac{(n-1)^2}{2}+(n-1)\right)F[n-1]+\left(\frac{n^2}{2} -\frac{(n-1)^2}{2}\right)\\n^2F[n] &= \left(n^2-1\right)F[n-1]+(2n-1)\\\end{align*}$$Chegamos finalmente em uma recorrencia sem