Análisis de la complejidad de los logaritmos

Question

Tengo dos funciones, f(n)=log(base 2)n y g(n)=log(base 10)n. Estoy tratando de decidir si f(n) es O(g(n)), o (g(n)) o (g(n)). Creo que debería tomar el límite f(n)/g(n) a medida que n va a infinito, y creo que ese límite es constante, por lo que f(n) debe ser (g(n)). ¿Estoy en lo cierto? Gracias de antemano

Answer 1

Puede confiar en un resultado útil y a menudo olvidado, que $(\log_a b)(\log_b c) = \log_a c$ así que en tu problema tendremos $$ (\log_2 10)g(n) = (\log_2 10)(\log_{10} n) = \log_2 n = f(n) $$ así que $f(n)$ no es más que un múltiplo constante ( $\log_2 10\approx 3.32$ ) de $g(n)$ y por lo tanto $f(n)=\Theta(g(n))$ .