Bonsoir à tous!

J'espère que je pourrai trouver la réponse à mon problème ici. Ça fait maintenant quelques heures que je tourne autour mais sans succès. Voici l'exercice en question :

Prouver ou trouver un contre-exemple pour ce qui suit :

Si f1, f2, g1, et g2 sont des fonctions de N dans R tel que f1(n) est Big-Theta de g1(n) et f2(n) est Big-Theta de g2(n), alors f1(n) - f2(n) est Big-Theta de g1(n) - g2(n).

Citation : Cedrat

Si f1, f2, g1, et g2 sont des fonctions de N dans R tel que f1(n) est Big-Theta de g1(n) et f2(n) est Big-Theta de g2(n), alors f1(n) - f2(n) est Big-Theta de g1(n) - g2(n).

Qu'est ce que c'est Big-Theta ?

Définition de O
<math>\(f(n) \in O \left( g(n) \right) \Leftrightarrow \exists c > 0, n_0 > 0 : \forall n \geq n_0, f(n) \leq c g(n)\)</math>

Définition de <math>\(\Omega\)</math>
<math>\(f(n) \in \Omega \left( g(n) \right) \Leftrightarrow \exists c > 0, n_0 > 0 : \forall n \geq n_0, f(n) \geq c g(n)\)</math>

Définition de <math>\(\Theta\)</math>
<math>\(f(n) \in \Theta \left( g(n) \right) \Leftrightarrow \exists c_1, c_2 > 0, n_0 > 0 : \forall n \geq n_0, c_1 g(n) \leq f(n) \leq c_2 g(n)\)</math>

Merci Gr3n@d1n3 pour les définitions. Ceci dit, je me demande si elles ne sont pas uniquement valables lorsque f et g sont en valeur absolue ?

Je les ai trouvées sans valeur absolue (lien). Après, il y a peut-être d'autres formulations...

Sinon, pour ton problème, je suis partie dans la recherche d'un contre-exemple parce que ça me paraissait faux, mais pour l'instant sans succès...

Ça peut-être vrai mais en cours on n'a vu ces définitions qu'avec des valeurs absolues, donc je doute que je puisse utiliser celles-ci.

Sinon ben j'ai aussi commencé par essayer de trouver des contre-exemples mais franchement j'ai beau tenter les fonctions les plus improbables, rien n'y fait. Donc forcément je me dis que ca doit être juste.

Sachant que : |f1(n)| <= C1*|g1(n)| pour n > k1, et |f2(n)| <= C2*|g2(n)| pour n > k2

J'en arrive au point ou |f1(n) - f2(n)| <= C1*|g1(n)| - C2*|g2(n)| (En premier je veux démontrer que la partie f1 - f2 est O(g1 - g2)). Et là je bloque, j'arrive pas à trouver un moyen de mettre g1 - g2 dans la même valeur absolue.

Tu peux dire que puisque |f1|-|f2| <= C1|g1|-C2|g2|, alors |f1|-|f2| <= ppcm(C1C2)(|g1|-|g2|) puis avec l'inégalité triangulaire, |g1|-|g2| <= |g1-g2| donc |f1|-|f2| <= ppcm(C1C2)|g1-g2|.
Ça c'est por la partie big-O, pour le big-Omega je bloque un peu.

Exactement! Je pensais plus à trouver une h en fonction de g1, g2 qu'une constante en fonction de C1, C2. Merci en tout cas.

Pour le Big-Omega est-ce que ce serait juste d'écrire :
|f1| - |f2| >= C1'.|g1| - C2'.|g2| sachant que |f1| >= C1'.|g1| et |f2| >= C2'.|g2| ? J'ai conscience que c'est une question un peu bébête mais par exemple : 5 >= 5 et 2 >= 1 mais 5-2 < 5-1 (Idem pour le cas de Big-O). C'est plus le coté "ou égal" de l 'inégalité qui pose problème.

il n'y a pas de valeurs absolues, sinon :
f1(n)=g1(n)=g2(n)=n
f2(n)=-n
on a bien f1 et f2 theta de g1 et g2 selon ta définition avec les valeurs absolues mais on n'a pas 2n theta de 0.

P.S.: en français on dit grand au lieu de big

EDIT : je viens de voir la superbe réponse de Venk :

Citation : Venk

Tu peux dire que puisque |f1|-|f2| <= C1|g1|-C2|g2|, alors |f1|-|f2| <= ppcm(C1C2)(|g1|-|g2|) puis avec l'inégalité triangulaire, |g1|-|g2| <= |g1-g2| donc |f1|-|f2| <= ppcm(C1C2)|g1-g2|.
Ça c'est por la partie big-O, pour le big-Omega je bloque un peu.

Il utilise ici une inégalité intéressante : C1|g1|-C2|g2| <= ppcm(C1C2)(|g1|-|g2|).
Je ne la connaissait pas mais elle semble très puissante et permet de montrer plein de trucs que je pensais faux :
prenons C1 = 2, C2 = g1 = g2 = 1 et on obtient 1 <= 0
De plus que signifie ppcm(C1,C2) alors que C1 et C2 sont des réels ?

f1(n)=g1(n)=f2(n)=1
Je te laisse choisir g2 (histoire de chercher un peu).

En lisant, peut être un peu vite, je relève ce genre d'affirmation:

Citation

Sachant que : |f1(n)| <= C1*|g1(n)| pour n > k1, et |f2(n)| <= C2*|g2(n)| pour n > k2

J'en arrive au point ou |f1(n) - f2(n)| <= C1*|g1(n)| - C2*|g2(n)|

Soustraire des inégalités pour en obtenir une nouvelle me paraît pour le moins fautif, à moins que j'ai raté une hypothèse ?

Quant à l'assertion elle me semble fausse .
Des contre exemples ... des fonctions constantes et g1 = g2 ?

Non, c'est effectivement faux, je me suis un peu emballé...

Il me parait également, après vos commentaires, que c'est bien faux. Merci les gens!