"Big Oh notation"

[Adaltian]

Bonjour à tous,

Je suis tombé sur cette définition :
T(n)=O(f(n)) <=> Il existe des constantes c et No>0 pour lesquelles on a T(n)<= c*f(n) pour tout n>=No

>= veut dire supérieur ou égal, <=> signifie l'équivalence. (On sait jamais, jamais claires les mat' par internet)

Je voulais savoir si elle était équivalente à :
Il existe une constante c pour laquelle la limite en + l'infini de c*f(n) - T(n) est supérieure ou égale à 0.

Si oui, ça m'aiderait à simplifier beaucoup de choses dans les démonstrations x)


Merci à tous !

[Monsieur23]

Aloha,

Non, ce n'est pas équivalent : dans ta seconde définition, tu dit que la suite (T(n)/f(n)) a une limite, qui est positive. Dans la première, tu n'as pas d'existence de limite, juste que la suite est bornée.

[adrien69]

Salut, alors déjà la définition du O ça sous-entend des valeurs absolues partout :
(On dit que T(n) contrôle f(n) quand on parle informellement)

Pour ce qui est de ta question, non. Pour deux raisons : la limite peut ne pas exister (dans le sens être infinie ou dans l'autre sens) et une autre. Par exemple : f(n)=1 si n est pair, 0 si n est impair () et T(n)=1 pour tout n. On a bien f(n)=O(T(n)) mais la limite de |f(n)|-c|T(n)| n'existe pas. Pour ce qui est de la limite infinie je te laisse trouver un exemple (plus simple)

L'autre raison : c'est que dans le cas où la limite que tu as mentionnée existe, c'est assez vrai sauf si T(n) titille trop 0, mais ce n'est jamais la même constante qui intervient. Je m'explique.
Si avec l positif ou nul, alors pour a quelconque (on le choisira de telle manière que l-a>0 par exemple, ce qui implique par l'inégalité triangulaire que ce qui n'est borné (définition du O) que si T(n) ne se trouve jamais trop proche de 0 à partir d'un certain rang.

Tu as compris ?

En bref ce sont deux notions voisines, mais qui ne s'impliquent vraiment ni l'une ni l'autre.

[Adaltian]

Merci, j'ai saisi la nuance !

Une bonne journée ^^


adrien : Je viens de voir le cas supplémentaire que tu apportes

Merci à vous deux, ça fait plaisir de voir des gens aider ^^

[adrien69]

Aloha,

Non, ce n'est pas équivalent : dans ta seconde définition, tu dit que la suite (T(n)/f(n)) a une limite, qui est positive. Dans la première, tu n'as pas d'existence de limite, juste que la suite est bornée.

Nan c'est pas vrai, comme je l'ai montré dans mon gros pavé dont tu viens de casser l'effet :p