Qu'est-ce qu'une limite supérieure asymptotiquement serrée?

D'après ce que j'ai appris, la liaison asymptotiquement étroite signifie qu'elle est liée par le haut et par le bas comme dans la notation thêta. Mais que signifie la limite supérieure asymptotiquement serrée pour la notation Big-O?

Dire qu'une borne big-O est "asymptotiquement serrée" signifie essentiellement que l'auteur aurait dû écrire . Par exemple, O ( x 2 ) signifie que ce n'est pas plus que quelques instants constants  x 2 pour tous suffisamment grands  x ; "serré asymptotiquement" signifie qu'il s'agit en réalité de temps constants  x 2 pour suffisamment grand  x et non, disons, de temps constants  x 1,999 .$\Theta(-)$$O(x^2)$$x^2$$x$$x^2$$x$$x^{1.999}$

Voici un exemple qui l'explique (et un exemple concret pour la bonne réponse de David).

$A$$O(n^3)$$n$$A$$O(n)$$\Omega(n)$ , nous pourrions être plus précis et dire que l'algorithme prend$\Theta(n)$