¿Hay que demostrar la condición de igualdad para la notación Big-O?

Question

Según tengo entendido, $$T(n) = O(g(n)) \quad\text{iff}\quad T(n) \leq cg(n),$$ donde $c > 0$ y $n >N. $

Mi confusión es simple. Para demostrar que esto es cierto, ¿por qué no debemos demostrar la igualdad? Si no demostramos la igualdad en absoluto y simplemente mostramos que $T(n) < cg(n)$ para un conjunto de $n$ y $c$ entonces no implicaría que probar $T(n)$ satisface la condición de la notación small-o lo haría también para la notación Big-O?

Answer 1

Están ocurriendo dos cosas.

En primer lugar, demostrar que $T(n) = o(g(n))$ hace implican que $T(n) = O(g(n))$ . Aunque lo escribamos con $=$ debido a una confusa elección histórica de la notación, la notación big-O es siempre un límite superior.

Diciendo $T(n) = o(g(n))$ dice " $T(n)$ crece más lentamente que $c g(n)$ como $n \to \infty$ ".

Diciendo $T(n) = O(g(n))$ dice " $T(n)$ crece más lentamente o igual que $c g(n)$ como $n \to \infty$ ." La segunda afirmación incluye la primera.

A menudo, tratamos de exponer la mejor podemos utilizar grandes $O$ notación. Pero si lo que se pretende es captar la tasa exacta de crecimiento de $T(n)$ hasta un factor constante, realmente deberías estar escribiendo $T(n) = \Theta(g(n))$ .

---

Por otro lado, demostrar que hay $c>0, N$ tal que $T(n) \le c g(n)$ si $N>n$ es lo mismo que demostrar que hay $c>0, N$ tal que $T(n) < c g(n)$ si $N>n$ . No hay diferencia entre $<$ y $\le$ aquí.

Eso es porque si tienes $T(n) \le c g(n)$ para una constante $c$ entonces $T(n) < c g(n)$ para una constante ligeramente mayor $c$ . Por ejemplo, si alguien le dijera que $T(n) = O(n^2)$ porque $T(n) \le 3n^2$ para $n>1000$ También sabrá que $T(n) < 3.1n^2$ para $n>1000$ porque $3n^2 < 3.1n^2$ .

Answer 2

Big O es sólo un límite superior. Por ejemplo, es cierto que $n^2=O(2^n)$ aunque ambas funciones estén muy alejadas.

Si quieres decir que tienes un límite superior óptimo, eso sería un gran Theta, no sólo un gran O. Decimos $f(n)=\Theta(g(n))$ si existe $0<c_1<c_2$ tal que $c_1g(n)\leq f(n)\leq c_2g(n)$ para $n$ suficientemente grande.