¿Qué es un límite superior asintóticamente apretado?

Por lo que he aprendido, la unión asintóticamente estrecha significa que está unida desde arriba y desde abajo como en la notación theta. Pero, ¿qué significa el límite superior asintóticamente ajustado para la notación Big-O?

Decir que un límite big-O es "asintóticamente apretado" básicamente significa que el autor debería haber escrito . Por ejemplo, O ( x 2 ) significa que no es más que algunas veces constantes  x 2 para todos los suficientemente grandes  x ; "asintóticamente apretado" significa que realmente es algunas veces constantes  x 2 para x suficientemente grande  y no, por ejemplo, algunas veces constantes  x 1.999 .$\Theta(-)$$O(x^2)$$x^2$$x$$x^2$$x$$x^{1.999}$

Aquí hay un ejemplo que lo explica (y un ejemplo concreto de la buena respuesta de David).

Suponga que tiene un algoritmo que se da como entrada una matriz de enteros . El algoritmo explora la matriz e incrementa un contador inicialmente establecido en cero cada vez que ve un elemento que es un número entero par. Podemos probar las carreras del algoritmo en digamos O ( n 3 ) el tiempo, donde n es el número de elementos en una . Pero también podemos dar un límite más estricto y decir que se ejecuta a tiempo O ( n ) . Este límite es asintóticamente apretado: de hecho, ya que leer la entrada ya lleva Ω ( n Θ ( n ) tiempo.$A$$O(n^3)$$n$$A$$O(n)$$\Omega(n)$$\Theta(n)$