Totorial de Combinatória Analítica

Se você jogar Cara ou Coroa várias vezes em sequência, qual a chance de nunca aparecer duas caras seguidas?

Esse é um problema que você resolve com ferramentas da Combinatória. Se você estudou para o vestibular, certamente deve lembrar que esse tipo de problema usualmente se resolvia com permutações, arranjos ou combinações.

Infelizmente, isso é verdade no vestibular, mas não na vida real. Os problemas avançados de Combinatória resistem a essas ferramentas básicas. Em geral, você vai precisar de recorrências complexas e somatórias complicadas; e até recentemente não tinha nenhum método que fosse simples e geral, para usar em qualquer situação.

A boa notícia é que isso mudou! Nos últimos anos, surgiu um novo ramo da matemática, chamado de Combinatória Analítica, que permite calcular esses problemas com facilidade. Como ainda não existe nenhum texto introdutório em português, resolvi escrever um totorial para mostrar como as coisas ficam bem simples com esse método!

Um exemplo simples

Como funciona esse método novo? A analogia mais simples é com desenho geométrico. Com as técnicas tradicionais, você precisa de régua, compasso e uma boa dose de insight para resolver os problemas. Ao invés disso, você pode usar geometria analítica: o problema é transformado em uma série de equações, aí você não precisa pensar, só resolver (e em muitos casos nem precisa resolver, é só jogar num sistema de computação automática como o Wolfram Alpha que ele resolve para você).

Com combinatória analítica é parecido: você vai transformar a descrição do seu problema de contagem em uma equação, e aí existem técnicas padrão para resolvê-la. Para mostrar como funciona, vamos pegar um problema simples: Quantas strings binárias de tamanho ##n## existem?

Para ##n=3##, por exemplo, existem oito strings: ##000##, ##001##, ##010##, ##011##, ##100##, ##101##, ##110## e ##111##.

A primeira coisa a ser feita é caracterizar o conjunto de todas as strings. Podemos recursivamente construir as strings binárias válidas com três casos:

Caso 1: A string vazia (##\varepsilon##), ou...

Caso 2: Uma string que começa com ##0##, seguida de uma string válida, ou...

Caso 3: Uma string que começa com ##1##, seguida de uma string válida.

Pronto, agora podemos agora escrever a equação que descreve o conjunto ##B## das strings binárias. Em combinatória analítica, a regra é que a descrição "ou" vira adição, e a operação "seguida de" vira multiplicação. Vou também substituir o caractere ##0## por ##Z_0## e ##1## por ##Z_1## só para deixar claro que nesse contexto são átomos, e não números:
$$B=\varepsilon+Z_0\times B+Z_1\times B$$
Essa é a construção combinatória correspondente às strings binárias. Agora o pulo do gato: eu vou trocar ##\varepsilon## pelo número ##1##, cada átomo individual pela variável ##z##, e resolver a equação:
$$\begin{align*} B&=\varepsilon+Z_0\times B+Z_1\times B\\ B&=1+zB+zB\\ B&=\frac{1}{1-2z} \end{align*}$$
Chegamos então no elemento principal da combinatória analítica: a função geradora do conjunto das strings binárias. E por que ela é tão importante? É que essa função simples tem escondida dentro dela a solução do problema para qualquer ##n##! Basta expandir a função em série (nesse caso, basta reconhecer que essa é a fórmula da soma infinita de uma PG com razão ##2z##): 
$$B=\frac{1}{1-2z}=1+2z+4z^2+8z^3+16z^4+\cdots$$
Olha só, a solução aparece na série! O termo ##8z^3## significa que, para ##n=3##, a solução é ##8##, exatamente como tínhamos visto enumerando as possbilidades.

O operador SEQ

O método acima foi simples né? Mas dá para ficar mais fácil ainda! O pessoal que estuda combinatória analítica faz bastante tempo inventou uma série de operadores que deixam a solução mais fácil de escrever.

O primeiro deles é o operador ##SEQ##, que serve para definir sequências. Ao invés da definição recursiva com três casos, podemos simplesmente dizer que uma string binária é formada por uma sequência de zero ou mais átomos, onde os átomos possíveis são ##0## e ##1##. Daí a construção combinatória sai direto:
$$B=SEQ(Z_0+Z_1)$$
E como transformar isso em função geradora? Se você sabe que um conjunto ##A## tem função geradora ##A(z)##, então a função geradora da sequência de ##A## é: 
$$SEQ(A)=\frac{1}{1-A(z)}$$ 
No nosso caso, a função geradora das strings binárias é:
$$SEQ(Z_0+Z_1)=SEQ(z+z)=\frac{1}{1-2z}$$
Pronto, a função geradora saiu direto, sem precisar resolver nenhuma equação!

O teorema de transferência

Ainda resta o problema de abrir a função geradora em série. Nesse caso foi fácil porque conseguimos ver de cara que a função era a soma de uma PG, mas e em casos mais complicados?

Bem, resolver de maneira exata continua sendo um problema difícil até hoje. Mas na maioria das vezes você não precisa da solução exata, um assintótico para ##n## grande já é suficiente. E para isso a combinatória analítica possui uma série de teoremas de transferência, que dão a resposta assintótica da função geradora sem precisar abrir a série!

O teorema de transferência usado nesse caso é simples de usar, embora sua definição seja meio assustadora:

Se a sua função geradora for uma função racional ##f(z)/g(z)##, onde ##f(z)## e ##g(z)## são relativamente primas, ##g(0)\neq 0##, ##g(z)## tem um único pólo ##1/\beta## de módulo mínimo, e ##\nu## é a multiplicidade desse pólo, então um assintótico para a função é dado por: $$[z^n]\frac{f(z)}{g(z)}=\nu\frac{(-\beta)^\nu f(1/\beta)}{g^{(\nu)}(1/\beta)}\beta^n n^{\nu-1}$$

Eu juro que é simples, apesar de assustador. Para o nosso caso, ##f(z)=1##, ##g(z)=1-2z##, ##g'(z)=-2##, ##\beta=2##, ##f(1/2)=1##, ##g'(1/2)=-2## e ##\nu=1##. Substituindo os valores, temos:
$$[z^n]B(z)=1\times\frac{(-2)^1\times 1}{-2}\times(2)^n n^{1-1} =2^n $$
Portanto, existem ##2^n## strings binárias de tamanho ##n##, o que bate com nosso resultado de ##8## para ##n=3##.

Outro exemplo

E se eu quiser calcular quantas strings binárias existem, mas só as que não possuem dois zeros seguidos? Esse problema é complicado com combinatória tradicional, mas com combinatória analítica fica simples!

Primeiro, vamos caracterizar essas strings. Podemos descrevê-las como uma sequência de ##1## ou ##01##, seguida de ##0## ou vazio:
$$C=SEQ(Z_1+Z_0Z_1)\times(Z_0 + \varepsilon)$$
Traduzindo para função geradora:
$$C=SEQ(z+z^2)\times(z+1)=\frac{z+1}{1-z-z^2}$$
Agora aplicamos o teorema de transferência. ##f(z)=z+1## e ##g(z)=1-z-z^2##. As raízes de ##g(z)## são ##0.618## e ##-1.618##, a de menor módulo é ##0.618## com multiplicidade ##1##. Então:
$$\begin{align*} \beta &= 1/0.618 = 1.618 \\ f(1/\beta)&=f(0.618)=1.618 \\ g'(z) &=-2z-1 \\ g'(1/\beta) &=g'(0.618)=-2.236 \\ C[n]&\sim \frac{-1.618\times 1.618}{-2.236}\times 1.618^n \\ C[n] &\sim 1.171\times 1.618^n \end{align*}$$
Prontinho, transformamos raciocínio, que é díficil, em álgebra, que qualquer chimpanzé bêbado consegue fazer!

A pergunta original

Podemos agora voltar à pergunta original: se você jogar Cara ou Coroa várias vezes em sequência, qual a chance de nunca aparecer duas caras seguidas?

Ora, essa probabilidade é exatamente igual ao número de strings binárias que não possuem dois zeros seguidos, dividida pelo número total de strings binárias. Esses são os dois casos que analisamos, logo:
$$p\sim\frac{1.171\times1.618^n}{2^n} = 1.171\times 0.809^n$$
Easy! E funciona mesmo? Eu fiz uma simulação computacional para comparar com o nosso assintótico, eis o resultado:

Para ##n=5##, simulação ##40.78\%##, assintótico ##40.57\%##.

Para ##n=10##, simulação ##14.17\%##, assintótico ##14.06\%##.

Para ##n=15##, simulação ##4.84\%##, assintótico ##4.87\%##.

Script com a simulação no github

Ou seja, funcionou super bem, e a precisão vai ficando melhor conforme o ##n## aumenta.

Para saber mais

Se você gostou do que viu, a referência definitiva sobre o tema é o livro Analytic Combinatorics, do Flajolet, que foi o inventor da técnica. Não é o livro mais didático do mundo, mas está inteiramente disponível na web. No Coursera, de tempos em tempos, o Sedgewick faz um curso online, que eu super recomendo, foi onde eu aprendi inclusive. E na wikipedia... o tópico é tão novo que não tem na wikipedia em português ainda! Fica como exercício para o leitor criar uma página na wikipedia sobre o tema :)

A Busca Por Bozo Binário

Se você trabalhar por tempo o suficiente com Computação, eventualmente uma das suas atribuições vai ser entrevistar candidatos para a sua equipe. Entrevistar é uma arte: existem inúmeros truques e macetes para descobrir se é esse sujeito na sua frente é mesmo o cara que você quer como seu parceiro. O Joel tem uma boa introdução sobre o tema que vale a pena ler.

Uma das habilidades que você precisa desenvolver rápido é aprender que o candidato não pensa como você. Em especial, quando ele responde uma pergunta de um jeito diferente daquele que você esperava, não quer dizer necessariamente que ele esteja errado. E esse caso eu já vi de perto, com o algoritmo que eu apelidei de Busca Por Bozo Binário.

Essa história aconteceu faz algum tempo. Eu estava na cantina conversando sobre entrevistas, quando alguém comentou que rejeitou um candidato porque ele não conseguiu implementar uma busca binária. Poxa, isso é grave mesmo! E qual o algoritmo errado que ele fez? A resposta foi essa:

"Sorteie um número de 1 até o tamanho do vetor, e verifique o elemento que tinha esse índice. Se for igual você achou, então retorna. Se for menor, repete para o lado esquerdo; se for maior, repete para o lado direito."

Isso é errado, me disseram, porque o pior caso é ##O(n)##. De fato, se o elemento que você quer achar é o primeiro, e o gerador de aleatórios retornar sempre o último, ele vai passar pelo vetor inteiro.

Mas nesse ponto eu tive que interromper: "Peraí! Você explicitou que queria ##O(\log n)## no pior caso? Se você não falou nada no enunciado, ele pode ter entendido que era ##O(\log n)## no caso médio, e aí o algoritmo dele está certo!"

Na hora ninguém botou fé que esse algoritmo de Busca por Bozo Binário era de fato ##O(\log n)##, então eu tive que voltar para casa e escrever a demonstração. Se você tem medo de Matemática Discreta, pule a caixa azul:

Para a Busca por Bozo Binário, nós queremos calcular qual é o valor médio do número de comparações que ele realiza. E como você começa uma análise de caso médio?

Primeiro você define as características da entrada: eu vou assumir que todos os casos estão distribuídos uniformemente. Depois, é só usar a fórmula do valor esperado: você soma o número de comparações em cada caso, multiplicado pela probabilidade daquele caso ocorrer. $$ F[x] = \sum_i p[i]C[i] $$ Antes de começar, vejamos os casos extremos. Quando o vetor é vazio, não precisa de nenhuma comparação, então ##F[0]=0##. Se o vetor tiver tamanho um, então só precisa de uma comparação, ##F[1]=1##. É sempre bom ter uns casos pequenos para conferir no final.

Vamos ver agora o caso de um vetor de tamanho ##n##. Eu não sei qual número vai ser escolhido para cortar o vetor em dois, é o gerador de números aleatórios que escolhe. Então eu vou tirar a média sobre todas as escolhas possíveis. Como os ##n## valores são equiprováveis, então a probabilidade individual é ##1/n##: $$F[n] = \sum_{0\le k\lt n}\frac{1}{n}F[k,n] = \frac{1}{n}\sum_{0\le k\lt n}F[k,n] $$ Na fórmula acima, ##F[n]## é o número médio de comparações para um vetor de tamanho ##n##, e ##F[k,n]## é o número médio de comparações 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 está o número que estamos procurando. Eu não sei onde está o número; como estamos calculando o caso médio, precisamos tirar a média sobre todos as posições possíveis. $$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 médio para um vetor de tamanho ##n##, cortado na posição ##k##, e com número final na posição ##i##.

Nós temos três casos agora. Se ##i=k##, então você só precisa comparar uma vez, a comparação vai ser verdadeira e o algoritmo termina. Se ##i\lt k##, então você compara uma vez e faz recursão para o lado esquerdo. Se ##i\gt k##, então você compara uma vez e faz recursão 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 única recorrência. $$\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 é só resolver!

Antes de mais nada, vamos coletar quem é constante em relação ao índice da somatória. Todos os ##1/n## coletam, e as somatórias 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 somatória. 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 é só manipular os índices: $$\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 só, a segunda somatória é igual à 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 fórmula 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 somatória ainda está atrapalhando, o ideal seria sumir com ela. Uma maneira de fazer isso é 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 última fórmula vale para todo ##n##, em especial vale também 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*}$$ Ahá! Agora é só subtrair uma da outra que a somatória 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 recorrência sem somatórias. Melhor ainda, essa recorrência está no ponto certo para usar a técnica do summation factor! Como esse é um truque muito útil de se conhecer, eu vou fazer em câmera lenta. Você pode usar um summation factor sempre que sua recorrência for da forma abaixo: $$a_n F[n] = b_n F[n-1]+c_n$$ Esse é o nosso caso, se usarmos a correspondência abaixo: $$\begin{align*} a_n &= n^2 \\ b_n &= n^2-1 \\ c_n &= 2n-1 \end{align*}$$ O segredo do summation faction é tentar achar uma sequência mágica ##s_n## que tenha a seguinte propriedade: $$s_n b_n=s_{n-1}a_{n-1}$$ E por que isso é bom? Olha só o que acontece quando você multiplica a recorrência original por ##s_n##: $$\begin{align*} a_n F[n] &= b_n F[n-1]+c_n \\ s_n a_n F[n] &= s_n b_n F[n-1]+s_n c_n \\ s_n a_n F[n] &= s_{n-1}a_{n-1}F[n-1]+s_n c_n \\ \end{align*}$$ Agora, se você substituir ##T[n]=s_n a_n F[n]##, temos: $$\begin{align*} s_n a_n F[n] &= s_{n-1}a_{n-1}F[n-1]+s_n c_n \\ T[n] &= T[n-1]+s_n c_n \end{align*}$$ Opa, essa é fácil! Dá pra resolver de cabeça, é praticamente a definição de somatória! $$\begin{align*} T[n] &= T[n-1]+s_n c_n\\ T[n] &= T[0] + \sum_{1\le k \le n} s_k c_k \\ s_n a_n F[n] &= s_0 a_0 F[0] + \sum_{1\le k \le n} s_k c_k \\ F[n] &= \frac{1}{s_n a_n} \left(s_0 a_0 F[0] + \sum_{1\le k \le n} s_k c_k \right) \\ \end{align*}$$ Pronto, agora não é mais uma recorrência, é uma fórmula simples. A dificuldade do método é encontrar o tal do ##s_n##. Para achá-lo você pode usar a intuição, chutar, fazer um sacrifício aos deuses; ou então você pode usar o método do porradão. Nesse método você começa com ##s_n=s_{n-1}\left(a_{n-1}/b_n\right)## e abre recursivamente, chegando no monstrinho abaixo: $$s_n = \frac{a_{n-1}a_{n-2}\ldots a_2 a_1}{b_n b_{n-1}\ldots b_3 b_2}$$ Essa fórmula parece grande, e é grande mesmo. Mas na maioria das vezes tem um monte de cancelamentos, o que deixa o resultado final pequeno. Vamos ver no nosso caso como fica: $$\begin{align*} s_n &= \frac{a_{n-1}a_{n-2}\ldots a_2 a_1}{b_n b_{n-1}\ldots b_3 b_2} \\ &= \frac{(n-1)^2 (n-2)^2 \ldots 2^2 1^2} {\left(n^2-1\right) \left(\left(n-1\right)^2-1\right) \ldots (3^2-1) (2^2-1)} \\ &= \frac{(n-1)^2 (n-2)^2 \ldots 2^2 1^2} {\left((n+1)(n-1)\right) \left((n-1+1)(n-1-1)\right) \ldots (3+1)(3-1) (2+1)(2-1)} \\ &= \frac{(n-1) (n-2)(n-3) \ldots3\cdot 2\cdot 1} {(n+1) (n) (n-1)\ldots (4+1) (3+1) (2+1)} \\ &= \frac{2} {(n+1) (n) } \\ \end{align*} $$ Cancelou mesmo! Bastou lembrar que ##(a^2-b^2)=(a+b)(a-b)## que o resto saiu. Agora é só lembrar que ##F[0]=0## e substituir na fórmula: $$\begin{align*} F[n] &= \frac{1}{s_n a_n} \left(s_0 a_0 F[0] + \sum_{1\le k \le n} s_k c_k \right) \\ F[n] &= \frac{n(n+1)}{2n^2} \sum_{1\le k \le n} \frac{2(2k-1)}{k(k+1)}\\ \end{align*}$$ Essa é a solução da recorrência. Dá para achar uma forma fechada? Nesse caso dá, desde que você tope uma forma fechada em função dos números harmônicos ##H[n]##, que são definidos como: $$H[n]=\sum_{1\le k \le n}\frac{1}{k}$$ Você começa abrindo a fração no somatório: $$\begin{align*} \frac{2(2k-1)}{k(k+1)} &= \frac{A}{k} + \frac{B}{k+1}\\ \frac{4k-2}{k(k+1)} &= \frac{A(k+1)+B k}{k(k+1)}\\ 4k-2 &= Ak+A +B k \\ 4k-2 &= (A+B)k+A \\ A &= -2 \\ B &= 6 \end{align*}$$ Agora você divide o somatório em dois: $$\begin{align*} F[n] &= \frac{n(n+1)}{2n^2} \sum_{1\le k \le n} \frac{2(2k-1)}{k(k+1)}\\ F[n] &= \frac{n(n+1)}{2n^2} \sum_{1\le k \le n} \frac{6}{k+1} - \frac{2}{k}\\ F[n] &= \frac{n(n+1)}{2n^2} \left( \sum_{1\le k \le n} \frac{6}{k+1} - \sum_{1\le k \le n} \frac{2}{k} \right) \\ F[n] &= \frac{n(n+1)}{2n^2} \left( \sum_{1\le k \le n} \frac{6}{k+1} - 2\sum_{1\le k \le n} \frac{1}{k} \right) \\ F[n] &= \frac{n(n+1)}{2n^2} \left( \sum_{1\le k \le n} \frac{6}{k+1} - 2H[n] \right)\\ \end{align*}$$ O primeiro somatório precisa de um pouco de massagem: $$\begin{align*} \sum_{1\le k \le n} \frac{6}{k+1} &= \sum_{1\le q-1 \le n} \frac{6}{q} \\ &= \sum_{2\le q \le n+1} \frac{6}{q} \\ &= -6+\frac{6}{n+1}+6\sum_{1\le q \le n} \frac{1}{q} \\ &= -6+\frac{6}{n+1}+6H[n] \\ \end{align*}$$ Por fim: $$\begin{align*} F[n] &= \frac{n(n+1)}{2n^2} \left( \sum_{1\le k \le n} \frac{6}{k+1} - 2H[n] \right)\\ F[n] &= \frac{n(n+1)}{2n^2} \left( -6+\frac{6}{n+1}+6H[n] - 2H[n] \right)\\ F[n] &= -3 +\frac{2(n+1)}{n}H[n]\\ \end{align*}$$ Ufa, deu trabalho! E isso é ##O(\log n)## mesmo? Bem, podemos verificar usando um assintótico para o harmônico, por exemplo: $$ H[n] = \ln n + \gamma + O(1/n) $$ Agora você substitui: $$\begin{align*} F[n] &= -3 +\frac{2(n+1)}{n}H[n]\\ &= -3 +2H[n] +\frac{H[n]}{n} \\ &= -3 +2\ln n +2\gamma +O(1/n)+ 2\frac{\ln n}{n}+2\frac{\gamma}{n}+O(1/n^2) \\ &= 2\ln n + O\left(\frac{\ln n}{n}\right) \\ &= O(\log n) \end{align*}$$ Como queríamos demonstrar!

Ou seja, realmente a Busca por Bozo Binário é ##O(\log n)##. Em demonstrações grandes assim eu sempre gosto de fazer uma simulação por Monte Carlo para conferir as contas. A minha simulação está no github:

Busca por Bozo Binário, simulação por Monte Carlo

Simulando 50000 vezes em um vetor de tamanho 3000, o número médio de comparações foi de ##14.1769##. O valor teórico previsto pela fórmula é de ##14.1732##, nada mau!

Eu também fiz uma simulação da busca binária tradicional como comparação. Com os mesmos parâmetros, a busca tradicional usou ##10.6356## comparações no caso médio, ou seja, foi mais eficiente que o Bozo Binário.

Por que isso acontece? Analisando o assintótico fica claro. Para ##n## grande, o valor médio da Busca por Bozo é de ##2 \ln n## (logaritmo natural), enquanto que na busca binária é ##\log_2 n## (logaritmo de base 2). Então, em média, esperamos que Bozo Binário seja mais lento por um fator de:

$$\begin{align*} \frac{2\ln n}{\log_2 n} &= {2\frac{\log n}{\log e}} \div {\frac{\log n}{\log 2}} \\ &= 2\frac{\log n}{\log e} \times \frac{\log 2}{\log n} \\ &= 2\frac{\log 2}{\log e} \\ &= 2\ln 2 \\ &\simeq 1.386 \end{align*}$$ Ou seja, mais ou menos uns 38% mais lento, o que bate com a simulação.

Depois da análise do algoritmo, a dúvida que resta é: e o candidato? Bem, se fosse eu a entrevistar, precisaria coletar mais dados para saber se ele realmente sabia do tempo médio, ou se estava perdido e implementou a primeira coisa que veio na cabeça.

Um possível follow-up é "Certo, esse método é mais complicado que a busca binária tradicional, mas funciona. Você pode me falar alguma situação onde ele é preferível sobre o tradicional?". Curiosamente, existe sim um caso onde a Busca por Bozo Binário é melhor que a busca binária tradicional! Mas esse caso fica para a próxima :)