Tarjetas de memoria: Relations de comparaison des suites — 11 tarjetas

Qu'impose la domination d'une suite x par y ?

La suite (x_n/y_n) est bornée avec y_n non nul à partir d'un certain rang.

Domination: notation

x=O(y), suite bornée par y

Que signifie x=o(y) pour deux suites x et y ?

La suite (x_n/y_n) converge vers 0 avec y_n non nul à partir d'un certain rang.

Négligeabilité: définition

x=o(y), quotient tend vers 0

Que signifie $n^\alpha=o(n^\beta)$ si $\alpha<\beta$ ?

La suite $n^\alpha$ est négligeable devant $n^\beta$.

Négligeabilité implique

x=o(y) implique x=O(y)

Que vaut la relation entre $a^n$ et $b^n$ si $0<a<b$ ?

La suite $a^n$ est négligeable devant $b^n$.

Suite régulière comparison

α<β ⇒ n^α=o(n^β)

Exponential comparison

a^n=o(b^n) si 0<a<b

Suite factoriel comparaison

a^n=o(n!), n! =o(n^n)

Transitivité en O et o

x=O(u), u=O(v) ⇒ x=O(v)