Complexité

[banzkura]

Bonjour,

J'aimerai savoir quelque chose.
Est ce que log(n) est O(n) ?
Si oui, comment le prouver?

Merci.
-----

[gg0]

Oui,

avec une constante aussi petite que tu veux, car log(n)=o(n). Preuve : la définition et une propriété connue dès la terminale de lycée (la limite à l'infini de ln(x)/x).

Cordialement.

Nb : il serait bon que tu réfléchisses un peu aux questions avant de les poser. Tu peux éventuellement y répondre toi-même !
NBB : Quel rapport avec la complexité ? A priori aucun !