Notation asymptotique O et o:

[rvfranck]

Salut,

Je veux juste avoir vos reponses sur ceci, c'est un QCM.
1) f(n) - o(f(n)) = theta(f(n))

2) si f(n) = o(n), alors f(n) = O(n/log(log n))

3) si f(n) = o(g(n)) alors f(n) = O(c.g(n)) pour chaque c > 0

pour ma part:
1) faux
2) faux
3) vrai

Merci

[bruce.ml]

1 est vrai, 2 et 3 sont faux.

des contres exemples pour 2 et 3 :

2) f(n) = n/(log(log(log(n)))
f(n) = o(n) et f n'est pas un O de n/(log(log(n))

3) f(n) = 0, g(n) = n
f(n) = o(g(n)) mais 0 n'est pas un O(n)

La preuve du 1 se fait rapidement en utilisant les définitions.