Extension aux suites et notations de comparaison asymptotique

Le cas des suites

Les croissances comparees s'etendent naturellement aux suites, quand n entier tend vers +infini. On ajoute deux nouveaux termes dominants a la hierarchie : la factorielle n! et n^n.

Hierarchie complete : ln(n) << n^a (a>0) << a^n (a>1) << n! << n^n, quand n -> +infini.

Resultats a connaitre

• lim n->+infini n^a / b^n = 0 pour tout b>1 et tout reel a.
• lim n->+infini a^n / n! = 0 pour tout reel a.
• lim n->+infini n! / n^n = 0.

Exemple

Pour etudier lim n->+infini (3^n)/n!, on utilise directement le deuxieme resultat : la factorielle finit toujours par l'emporter sur une suite geometrique, quelle que soit sa raison.

Notations o(.) et O(.)

Pour formaliser ces comparaisons, on utilise les notations de Landau :

• u_n = o(v_n) signifie que u_n/v_n -> 0, c'est-a-dire que u_n est negligeable devant v_n.
• u_n = O(v_n) signifie que u_n/v_n reste borne.

Avec ces notations, les theoremes se reecrivent : ln(x) = o(x^n), x^n = o(e^x), et pour les suites, n! = o(n^n).

Piege classique

Ne pas croire qu'une croissance qui parait tres rapide, comme 1000^n, bat n!. Meme avec un facteur enorme, une suite geometrique a^n est toujours dominee par n! a partir d'un certain rang, car n! est un produit de n termes qui finissent par depasser a.