Da complexidade da busca binária

Gostaria de apresentar meus cálculos para descobrir a complexidade do famoso algoritmo de busca binária. A complexidade é uma medida da quantidade de operações básicas em termos de algum parâmetro de entrada. Em algum momentos definie-se como o comportamento assintótico dessa quantidade. Esse algoritmo, em específico, aplica-se a listas ordenadas e é notável pela baixa dependência (não assintótica), no pior caso, com o tamanho da lista. Vou tentar mostrar uma forma de calcular essa dependência sem necessitar do teorema mestre.

O algoritmo em si pode ser encontrado aqui na Wikipédia. Basicamente, a lista é divida em duas. O elemento do meio é utilizado é comparado com a chave buscada. Se for maior, a mesma coisa é feita na metade seguinte; se for menor, na metade anterior. Portanto, pra cada iteração destas divisões ocorre uma única operação. Podemos portanto escrever, para o número de operações básicas para uma lista de tamanho n,



Claro que o argumento de C(n) deveria ser inteiro, e por isso utilizei a função floor. Agora, vamos simplificar um pouquinho o problema e calcular C(n) apenas para um número limitado de parâmetros n:



Logo, podemos escrever



Para p = k,



invertendo a equação de define k. Portanto,



é o resultado de fato esperado. Como resolvemos toda a relação de recorrência usando C(1), calculamos o pior caso. Faça testes manualmente para verificar a veracidade da fórmula. Essas contas garantem C(n) para muitos valores de n, mas é forçar a barra esperar que algo semelhante valha sempre (de 0 a 1000, provamos para apenas 10 valores de n).

Vamos supor agora uma correção à expressão para n,




Interessante isso, não? A correção p pode ser, no máximo, o inteiro anterior à própria potência que acabamos de tratar. Continuando,



Usando a identidade



que vale sempre que podemos separar inteiros de reais no argumento da função floor. Vamos definir



para podermos escrever



Finalmente, fazendo p = k, temos



Portanto, chegamos finalmente a



Ou seja, acabamos de ver que



Como é verdade que



Portanto, chegamos enfim na fórmula mais geral



E pronto. Faça novos testes para verificar a veracidade, lembrando que esta contagem vale no pior caso do algoritmo. Este resultado sairia rapidamente pelo teorema mestre, mas acho interessante mostrar dessa forma principalmente porque muitas vezes aquele teorema não está dentro do escopo do estudo.