Complejidad temporal de un algoritmo: ¿es importante establecer la base del logaritmo?

Dado que solo hay una constante entre las bases de los logaritmos, ¿no está bien escribir $f(n) = \Omega(\log{n})$ , en lugar de , o cualquiera que sea la base?$\Omega(\log_2{n})$

Depende de dónde esté el logaritmo. Si es solo un factor, entonces no hace la diferencia, porque big-O o $\theta$ permite multiplicar por cualquier constante.

Si toma $O(2^{\log n})$ entonces la base es importante. En la base 2 tendrías solo $O(n)$ , en la base 10 se trata de $O(n^{0.3010})$ .

Debido a que la notación asintótica es ajena a los factores constantes, y cualquiera de los dos logaritmos difiere en un factor constante, la base no hace ninguna diferencia: $\log_a n = \Theta(\log_b n)$ para todo $a,b > 1$ . Por lo tanto, no es necesario especificar la base de un logaritmo cuando se utiliza la notación asintótica.

Como $\log_xy = \frac{1}{\log_y{x}}$ y$\log_x{y} = \frac{\log_z{y}}{\log_z{x}}$ , entonces $\frac{\log_a{n}}{\log_b{n}} = \frac{\log_n{b}}{\log_n{a}} = \log_a{b}$. As $\log_a{b}$ is positive constant (for all $a,b > 1$), so $\log_a{n} = \Theta(\log_b{n})$.

In most cases, it's safe to drop the base of the logarithm because, as other answers have pointed out, the change-of-basis formula for logarithms means that all logarithms are constant multiples of one another.

There are some cases where this isn't safe to do. For example, @gnasher729 has pointed out that if you have a logarithm in an exponent, then the logarithmic base is indeed significant.

I wanted to point out another case where the base of the logarithm is significant, and that's cases where the base of the logarithm depends directly on a parameter specified as input to the problem. For example, the radix sort algorithm works by writing out numbers in some base $b$, decomposing the input numbers into their base-$b$ digits, then using counting sort to sort those numbers one digit at a time. The work done per round is then $\Theta(n + b)$ and there are roughly $\log_b U$ rounds (where $U$ is the maximum input integer), so the total runtime is $O((n + b) \log_b U)$. For any fixed integer $b$ this simplifies to $O(n \log U)$. However, what happens if $b$ isn't a constant? A clever technique is to pick $b = n$, in which case the runtime simplifies to $O(n + \log_n U)$. Since $\log_n U$ = $\frac{\log U}{\log n}$, the overall expression simplifies to $O(\frac{n \log U}{\log n})$. Notice that, in this case, the base of the logarithm is indeed significant because it isn't a constant with respect to the input size. There are other algorithms that have similar runtimes (an old analysis of disjoint-set forests ended up with a term of $\log_{m/2 + 2}$ somewhere, for example), in which case dropping the log base would interfere with the runtime analysis.

Another case in which the log base matters is one in which there's some externally-tunable parameter to the algorithm that control the logarithmic base. A great example of this is the B-tree, which requires some external parameter $b$. The height of a B-tree of order $b$ is $\Theta(\log_b n)$, where the base of the logarithm is significant in that $b$ is not a constant.

To summarize, in the case where you have a logarithm with a constant base, you can usually (subject to exceptions like what @gnasher729 has pointed out) drop the base of the logarithm. But when the base of the logarithm depends on some parameter to the algorithm, it's usually not safe to do so.