O(1) négligeable devant o(ln(n)) ?
Réponses à toutes vos questions après le Bac (Fac, Prépa, etc.)
-
Menthix
- Membre Relatif
- Messages: 152
- Enregistré le: 25 Nov 2012, 19:16
-
par Menthix » 07 Sep 2017, 20:07
Bonjour,
j'ai décidément du mal avec la négociabilité et les équivalents. Au cours d'un exercice il m'a fallu montrer que
ln(n) + k + o(1) est équivalent en +oo à ln(n).
Pour cela j'aimerai montrer que k = o(ln(n)) (ça va de soi) mais j'ai plus de mal pour montrer que o(1) = o(ln(n)). Car si o(1) est une fonction qui tend vers 0 en +oo, rien ne nous dit qu'elle est négligeable devant ln.
Merci d'avance de votre réponse.

-
pascal16
- Membre Légendaire
- Messages: 6663
- Enregistré le: 01 Mar 2017, 12:58
- Localisation: Angoulème : Ville de la BD et du FFA. gare TGV
-
par pascal16 » 07 Sep 2017, 20:39
tu peux revenir à la base de la définition et diviser par ln(n) et monter que le 'reste' tend vers 0
un o(1) est a fortiori un O(1), alors si ça va de soit que k = o(ln(n)), ça va de soit que o(1) est un o(ln(n))
-
Pseuda
- Habitué(e)
- Messages: 3222
- Enregistré le: 08 Avr 2015, 12:44
-
par Pseuda » 07 Sep 2017, 23:11
Bonsoir,
ln(n) tend vers +oo et o(1) tend vers 0. Il parait intuitivement évident que o(1) est négligeable devant ln(n). Sinon, tu peux toujours revenir à la définition : une fraction dont le numérateur tend vers 0 et le dénominteur tend vers +oo.
Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 42 invités