Lo que más me cuesta es la notación Big-O (estoy usando este libro de Rosen para la clase en la que estoy).
A primera vista, el Big-O me recuerda a los derivados, a la tasa de cambio y a todo lo demás; ¿es éste un pensamiento adecuado? Si $f(n)$ es $O(g(n))$ ¿tendrían los derivados algún efecto sobre esto?
Básicamente, ¿hay algún buen recurso para aprender Big-O por primera vez?
Si entiendo mal este foro y necesito una pregunta específica, entonces:
Demostrar que si $f(n)\le g(n)$ para todos $n$ entonces $f(n) + g(n)$ es $O(g(n))$ . (prefiero entender cómo hacerlo que tener una respuesta a un problema).
EDITAR:
Mi intento de respuesta a mi pregunta específica utilizando l'Hôpital:
$$\lim_{x\to\infty} \frac{f'(x)}{f'(x) + g'(x)} = \lim_{x\to\infty} \frac{1}{g'(x)}.$$
2 votos
Un ejemplo de precaución que puede ayudar a intuir algo de Big- $O$ frente a las derivadas. Consideremos una función que une (suavemente) los puntos $$(0,0), (1,1), (3,1), (4,4), (7,4), (8,8), \dots, (2^k, 2^k), (2^{k+1}-1, 2^k), (2^{k+1}, 2^{k+1}) \dots.$$ En otras palabras, la función se mantiene plana durante largos periodos de tiempo, y luego salta para encontrarse con $y=x$ de nuevo. Una función de este tipo satisface $f(x)=O(x)$ pero la derivada de $f$ puede ser arbitrariamente grande (aunque la derivada de $g(x)$ no lo es). En otras palabras, Big- $O$ La anotación sólo dice algo sobre el crecimiento MEDIO, no el crecimiento en todos los lugares.