Manual del estudiante de Ingeniería en Sistemas de UTN/Diseño e Implementación de Estructuras de Datos/Guías prácticas/Complejidad computacional/Solución al ejercicio 6 de complejidad computacional

Por definición, $f(x)=O(g(x))$ cuando $x\to \infty$, si y solo si:

$\lim _{x\to \infty }{\frac {f(x)}{g(x)}}<\infty$

Hallamos entonces el límite:

$\lim _{n\to \infty }{\frac {3*(n+1)^{7}+2n\log n}{n^{7}}}=$

$=\lim _{n\to \infty }{\frac {3*(n+1)^{7}+2n\log n}{n^{7}}}$

$=\lim _{n\to \infty }{\frac {3*(n+1)^{7}}{n^{7}}}+\lim _{n\to \infty }{\frac {2n\log n}{n^{7}}}$

Por ser polinomios del mismo grado:

$=3+\lim _{n\to \infty }{\frac {2\log n}{n^{6}}}$

Por regla de l'Hopital

$=3+\lim _{n\to \infty }{\frac {2}{6n^{6}\ln 10}}=3$

$3<\infty \Rightarrow$ $f(x)=O(g(x))$ cuando $x\to \infty$