[Homework] Complexité et notation asymptotiques

[kosa_nostra]

Bonjour,

Je penses avoir bien compris les notations asymptotiques, cependant j'aimerais confirmation que ce que j'ai fait est juste:

Sachant k>=1, e>0 et c > 1, est ce que A = N(B), N pouvant être les 5 notations : O, o, Omega, w, O bar i.e:
O: majoration
o: majoration stricte
Omega: minoration
w: minoration stricte
O bar: encadrement ()

J'ai don quelques fonctions et il faut que je dises si la première est N(la seconde). Voila mes réponses:

    A               B
  n^k           c^n         : A = O(B) et A = o(B)
  sqrt(n)       n^sin(n)   : aucune
  2^n           2^(n/2)    : A = Omega(B) et A = w(B)
  n^lg(c)      c^lg(n)     : A = O(B), A = Omega(B) et A = Obar(B)
  lg(n!)         lg(n^n)    : A = O(B) et A = o(B)
  lg(n)^k      n^e         :celle la me pose problème

Pouvez vous me dire ce que vous en pensé (je ne suis pas sur d'être complet sur chaque couples A,B) ? Et me mettre sur la piste pour la dernière ?

Cordialement,
Kosa

[Franck Dernoncourt]

Tout est ok pour moi mais lu rapidement donc à prendre avec des pincettes.
lg(n)^k = o(n^e)

Qu'entends-tu par être complet sur chaque couples A,B ? Normalement une seule relation doit suffire. (par exemple A = Obar(B) implique que A = O(B) et A = Omega(B))

[kosa_nostra]

Merci pour votre réponse !
Cordialement,
Kosa