Démonstration comportement asymptotique.

[invite2c16634f]

Soit f et g des fonctions avec domaine et co-domaine l’ensemble des nombres naturels définies par f(n) = n √n et g(n) = n √n log 10 n si n est pair et g(n) = n si n est impair.

Démontrez que f(n) n’est pas dans O(g(n)) et g(n) n’est pas dans O(f(n)).
-----

[gg0]

Bonjour.

Je ne comprends pas tout ("co-domaine" ??), mais il semble qu'il s'agit simplement d'appliquer la définition de O. En utilisant sa négation.

Cordialement.

NB : Si tu commences ton exercice et bloques à un moment, viens t'expliquer, on pourra t'aider ...

[invite2c16634f]

Soit,

f(n) est O (g(n)),

si n est pair,
n = 2000, k = 1, c = 2
2000√2000 ≤ 2000√(2000. log2000 Vrai

Si n est impair,
n = 2001, k = 1, c = 2
2001√2001 ≤ 2001 Faux

Alors,

f(n) n'est pas O (g(n)) lorsque n est impair.
F(n) n'est donc pas O(g(n)).


Soit,

g(n) est O(f(n)),

Si n est impair :
n ≤ C (n√n)
Avec c = 2, k = 1, n = 2000
2000 ≤ 2 ( 2000√2000) Vrai

Si n est pair :
(n√n).log₁₀n ≤ C (n√n),

En divisant par n√n de chaque coté :
log₁₀n ≤ C,

....Quelque soit les valeurs choisies pour C et N l'on pourra trouver un X plus grand que C. Donc un tel C et tel N ne peuvent pas exister.

Au final, g(x) n'est pas O(f(x))

Voila que pensez vous de ma réponse ?

merci