Demostrar que $\log f(n)$ es $O(\log n)$ .

Question

Si $f(n)$ es cualquier polinomio en n con coeficientes positivos, ¿cómo podría demostrar que $\log f(n)$ es $O(\log n)$ ? Hace tiempo que tengo problemas para hacer esto.

Answer 1

Pista: Sea $d$ sea el grado de $f$ y que $M$ sea un límite superior de los coeficientes. Entonces $$f(n)\le (d+1)(M)(n^d).$$ Ahora toma el logaritmo.

Answer 2

He aquí una solución muy rápida. Como sabemos $f(n)$ es un polinomio en $n$ tenemos $f(n)=O(n^m)$ para algunos $m\in N$ . Es decir, hay una constante positiva $c: f(n) \leq cn^m$ para un $n$ . Tomando logaritmos en ambos lados, tenemos $\log f(n) \leq \log(c) + m \log(n)$ podemos reducirlo a $\log f(n) \leq (m+c) \log (n)$ . Esto demuestra su resultado.

Answer 3

En primer lugar, $f(n) = O(n^p)$ donde $p$ - grado $f$ significa que $\frac{f(n)}{n^p}\to C$ como $n\to\infty$ .

Entonces $\log(\frac{f(n)}{n^p})\to \log(C)$ y $\log(f(n)) - p\log(n)\to \log(C)$ , dividiendo por $\log(n)$ tienen $\frac{\log(f(n))}{\log(n)} \to p$ . En $p$ es constante obtenemos $\log(f(n)) = O(\log(n))$