La question est:

Montrer ou réfuter que pour deux fonctions f,g, si f n'est pas dans O(g) alors g est dans O(f).

Mon contre-exemple :

Let f(n) be   f(n) = n^2 : if n is even
                  or n^4 : if n is odd

Let g(n) be   g(n) = n^3

Ceci est un exemple pour f pas dans O(g) et g pas dans O(f). Mon exemple est-il faux ? Si oui, pourquoi? Avez-vous d'autres exemples ?

2
Oweys 14 févr. 2020 à 23:04

1 réponse

Meilleure réponse

Votre contre-exemple fonctionne. Une preuve pourrait ressembler à ceci :

Supposons que f soit O(g). Alors il existe une constante positive c et un n0 tels que pour n >= n0, f(n) <= c * g(n). Soit n' un entier impair supérieur ou égal à n0. On a alors n'^4 <= c * n'^3. Diviser les deux côtés par n'^3 donne n' <= c. Cependant, cela ne peut pas être vrai pour tout n' > n0 ; il y a donc même n supérieur à n0 pour lequel la condition n'est pas vérifiée, contradiction.

La preuve dans l'autre sens est similaire, sauf que vous divisez les deux côtés par n'^2.

Je pense que le genre de contre-exemple que vous avez identifié est bon pour cela ; une fonction qui oscille d'une quantité asymptotiquement croissante et une fonction qui se situe quelque part au milieu.

2
Patrick87 14 févr. 2020 à 20:22