Cuando se habla del comportamiento asintótico de una función, hay un espectro de lo preciso que se puede ser.
En un extremo, tienes " $f$ es una función", que es muy impreciso y no dice nada. En el otro extremo, tienes " $f = f$ que es muy preciso, pero quizá no sea tan útil. En algún punto intermedio, tienes $f \in O(g), f \in \Theta(g), f \sim g$ y así sucesivamente.
Con la notación Big-O, generalmente ocurre una de estas tres cosas:
- usted está dando un límite que es suficiente para la declaración que está tratando de demostrar
- estás dando un límite que se mantiene para una clase general de funciones, pero puede haber algunas funciones en esa clase para las que se mantiene un límite más agudo. Por ejemplo
$$ f(x) = f(0) + f'(0)x + O(x^2)$$
es cierto para todas las funciones suaves, pero si $f(x) = \cos(x)$ es más preciso $O(x^3)$ .
- Usted tiene una función específica en mente y está tratando de proporcionar una estimación tan buena que puede probar que es "agradable". Así que no $f \in O(f)$ ya que eso no es útil, pero tal vez vea una declaración como $f \in O(n^{1 + \epsilon})$ para todos $\epsilon > 0$
También hay que tener en cuenta que Big-O es sólo un límite superior. Si quieres hacer afirmaciones más precisas sobre la asintótica de una función, debes dar también un límite inferior. Así que se podría decir $f \in \Omega(g_1)$ y $f \in O(g_2)$ . Y si es posible, tendrá $g_1 = g_2$ y puedes decir $f \in \Theta(g_1)$ . Pero a veces no se puede demostrar esto (todavía). No es raro ver afirmaciones como " $n^2 \le f(n) \le n^2 \log n$ para $n \gg 0$ en una situación en la que se pueda demostrar que $f \in O(n^2 \log n)$ pero no son capaces de demostrar que $f \in O(n^2)$ .
Así que, para resumir, big-O depende de lo preciso que seas o necesites ser. Si quieres ser más preciso, debes dar un límite inferior y un límite superior.
