Complexidade temporal de um algoritmo: é importante declarar a base do logaritmo?

Como existe apenas uma constante entre as bases dos logaritmos, não é correto escrever , em oposição a , ou qualquer que seja o base pode ser?$f(n) = \Omega(\log{n})$$\Omega(\log_2{n})$

Depende de onde está o logaritmo. Se é apenas um fator, não faz diferença, porque big-O ou $\theta$ permite que você se multiplique por qualquer constante.

Se você usar $O(2^{\log n})$ , a base é importante. Na base 2 você teria apenas $O(n)$ , na base 10 é sobre $O(n^{0.3010})$ .

Como a notação assintótica é alheia a fatores constantes, e quaisquer dois logaritmos diferem por um fator constante, a base não faz diferença: $\log_a n = \Theta(\log_b n)$ para todos $a,b > 1$ . Portanto, não há necessidade de especificar a base de um logaritmo ao usar notação assintótica.

Como $\log_xy = \frac{1}{\log_y{x}}$ e$\log_x{y} = \frac{\log_z{y}}{\log_z{x}}$ , de modo $\frac{\log_a{n}}{\log_b{n}} = \frac{\log_n{b}}{\log_n{a}} = \log_a{b}$. Como$\log_a{b}$é constante positiva (para todos$a,b > 1$), então$\log_a{n} = \Theta(\log_b{n})$.

Na maioria dos casos, é seguro descartar a base do logaritmo porque, como outras respostas apontaram, a fórmula de mudança de base para logaritmos significa que todos os logaritmos são múltiplos constantes um do outro.

Existem alguns casos em que isso não é seguro. Por exemplo, @ gnasher729 indicou que se você tiver um logaritmo em um expoente, a base logarítmica é realmente significativa.

Queria apontar outro caso em que a base do logaritmo é significativa, e é nesses casos que a base do logaritmo depende diretamente de um parâmetro especificado como entrada para o problema. Por exemplo, o algoritmo de classificação radix funciona escrevendo números em alguma base $b$ , decompondo os números de entrada em seus dígitos da base $b$ e usando a classificação de contagem para classificar esses números, um dígito por vez. O trabalho realizado por rodada é então $\Theta(n + b)$ e há aproximadamente $\log_b U$ rodadas (onde $U$ é o número máximo de entradas máximo), portanto, o tempo de execução total é $O((n + b) \log_b U)$ . Para qualquer número inteiro fixo$b$ isso simplifica para$O(n \log U)$ . No entanto, o que acontece se$b$ não for uma constante? Uma técnica inteligente é escolher$b = n$ ; nesse caso, o tempo de execução simplifica para$O(n + \log_n U)$ . Desde$\log_n U$ =$\frac{\log U}{\log n}$ , a expressão geral simplifica para$O(\frac{n \log U}{\log n})$. Observe que, nesse caso, a base do logaritmo é realmente significativa porque não é uma constante em relação ao tamanho da entrada. Existem outros algoritmos que têm tempos de execução semelhantes (uma análise antiga de florestas desarticuladas terminou com um termo de$\log_{m/2 + 2}$algum lugar, por exemplo); nesse caso, largar a base de logs interferiria na análise de tempo de execução.

Outro caso em que a base de log é importante é aquele em que há algum parâmetro externo para o algoritmo que controla a base logarítmica. Um ótimo exemplo disso é a árvore B, que requer algum parâmetro externo $b$ . A altura de uma árvore B da ordem $b$ é $\Theta(\log_b n)$ , onde a base do logaritmo é significativa, pois $b$ não é uma constante.

Para resumir, no caso de você ter um logaritmo com uma base constante, geralmente você pode (sujeito a exceções como o que @ gnasher729 apontou) soltar a base do logaritmo. Mas quando a base do logaritmo depende de algum parâmetro do algoritmo, geralmente não é seguro fazê-lo.