Prouver que f (n) = o (g (n)) implique 2^f (n) = o (2^g (n))

Question

Je ne trouve pas de contre-exemple à cela, mais je ne connais pas un manière formelle de le prouver. Quelqu'un peut-il me conduire dans la bonne direction?

C'est d'ailleurs une notation "little-o". Ainsi, une limite stricte supérieure

f (n) = o (g (n)) implique 2 $^{f (n)} = o (2^{g (n}) $

Answer 1

je voudrais de faire la correction ici, je suis tombé sur mes vieilles notes et se rendre compte que ce que je l'ai dit est complètement faux

explication est la suivante:.

permet de dire f (n) = 2n et g (n) = n

donc selon le problème donné prendre le pouvoir des deux côtés et ce sera

• 2^2n = 2^n;
• 2^n * 2^n = 2^n;
• et il ne satisfait pas la condition asymptotique car le côté gauche n'est pas constamment comparable au côté droit.

Answer 2

Voici un contre-exemple:

f(n) = 1/n 
g(n) = 1 

Nous avons: f(n)/g(n) -> 0 quand n -> oo, si f et g vérifie: f(n) = o(g(n)).

Mais:

2^f(n) = 2^(1/n) -> 1 when n -> oo 
2^g(n) = 2^1  -> 2 when n -> oo 

Et cela conduit à:

[2^f(n)]/[2^g(n)] -> 1/2 when n -> oo 

Cela prouve que 2^f(n) != o(2^g(n)).