comment prouvez-vous que le grand thêta d'une série est son premier terme?

Question

si f (x) = (An) x^n + (An-1) x^(n-1) + ... + (A1) x + (A0) comment pouvez-vous prouver que f (x) est grand thêta (x^n). J'ai pensé à cela et on pourrait le faire en prouvant que f (x) grand O (x^n) et x^n grand O (f (x)). J'ai compris la preuve pour le premier (en utilisant l'inégalité triangulaire) mais je ne pouvais pas comprendre comment faire le dernier. Alternativement on pourrait prouver que f (x) est grand oméga (x^n). Je suis resté bloqué sur cette question et tous les indices ou indices que vous pourriez me donner aideraient grandement.

Answer 1

Vous pourriez prouver qu'il est à la fois grand O (x^n) et grand Omega (x^n).

Answer 2

Considérons | An x^n + A (n-1) x^(n-1) + ... |/| x^n | comme x -> oo.

L'expression devient très proche de | An | et si An n'est pas nul, alors pour x suffisamment grand, l'expression sera au moins | An |/2.

Answer 3

Pour prouver f (x) est O (x^n), observer que pour x> = 1, chaque 0 < = x^0, x^2, ... x^n < = x^n.

Par conséquent, f (x) < = (n + 1) * max (A_0 ... A_n) * x^n

Mais (n + 1) * max (A_0 ... A_n) est Pour prouver que x^n est O (f (x)) est en fait assez difficile, puisque ce n'est pas vrai sauf si A_n! = 0 .! Mais si A_n = 0, à démontrer:

x^n is O(An x^n + ... + A0 x^0) 

par certains théorèmes sur les limites que je ne peux pas être dérangé à l'autre, c'est tru e ssi

(1/An) x^n is O(x^n + ... + (A0/An) x^0) 

qui est vrai ssi

(1/An) x^n - ... - (A0/An) x^0 is O(x^n) [**] 

Mais maintenant, le LHS est un polynôme de la forme que nous venons de prouver est O (x^n) dans la première partie. QED.

En pratique, cependant, ce que vous faites en réalité prouve des lemmes sur la complexité big-O de la somme de deux fonctions avec des complexités big-O connues. Ensuite, vous observez simplement que tous les termes des deux côtés sont O (x^n), et vous pouvez ignorer le reste.

[*] C'est un fudge, en fait, puisque ce qui compte est la comparaison de la valeur absolue de la fonction. Mais pour x assez grand, f (x) a le même signe que A_n, donc si c'est négatif, nous faisons juste une inégalité similaire dans l'autre sens. Je ne pense pas que vous ayez vraiment besoin de l'utilisation de l'inégalité triangulaire pour "échapper" les abs, parce que les fonctions polynomiales sont nécessairement monotones en dehors d'une certaine plage (c'est-à-dire qu'elles ont seulement un nombre fini de points d'inflexion). Lorsque l'on considère les limites de big-O, nous nous intéressons uniquement à ce qui se passe en dehors d'une certaine plage.

[**] Un autre fudge, vraiment j'aurais dû écrire la constante de limite M sur le RHS, et je l'ai compris quand j'ai transposé les termes au LHS. OK, donc ce n'est qu'une esquisse d'une preuve.