Qual é o valor da base dos logaritmos nas notações assintóticas?

Ao representar a complexidade de um algoritmo, é comum nos depararmos com logaritmos nas notações assintóticas.

Por exemplo, a complexidade da pesquisa binária é $O(\log n)$. Mas qual é o valor da base desse logaritmo?

O fato é que a notação assintótica torna o valor da base irrelevante. Isso é uma consequência da propriedade da mudança de base dos logaritmos, já que logaritmos de um mesmo número em diferentes bases diferem apenas por uma constante multiplicativa [1].

No caso da busca binária, vamos supor que a base seja 10: $O(\log_{10} n)$. Agora, vamos mudar a base para 2:

$$\begin{align*}O(\log_{10} n)&=O\left(\frac{\log_2 n}{\log_2 10}\right)\\&=O\left(\log_2 n\times\frac{1}{\log_2 10}\right)\\&=O(\log_2 n)\end{align*}$$

Na última etapa, a constante $\cfrac{1}{\log_2 10}$ foi absorvida pela notação Big-O (o mesmo ocorreria se fosse a notação Θ ou Ω). Também concluímos que $O(\log_{10} n) = O(\log_2 n)$. Esse resultado pode ser estendido para outras bases e complexidades de outros algoritmos.

Respondendo a pergunta do título: se considerarmos as definições das notações assintóticas (Big-O, Θ, Ω), então qualquer valor real que satisfaça a definição dos logaritmos pode servir de base.

Por fim, essa "liberdade" para escolher a base é vantajosa, por exemplo, para resolver recorrências com o método de Akra-Bazzi, pois se a função de custo possuir um logaritmo, então podemos escolher uma base que seja conveniente para realizar a integração, como a constante de Neper.

Leia também: Teorema Mestre e Exemplos Resolvidos

Referências

[1] SODRÉ, U. (2006). ENSINO MÉDIO :: Logaritmos. Acesso em 5 de abril de 2018.