Si f(n) = o(g(n)) , alors 2^(f(n)) = o(2^(g(n)))?

Avis que je demande pour peu-o ici (voir question similaire ici) - pour les grands Oh, c'est clairement pas peu o il se sent le droit mais ne semble pas possible de le prouver...

EDIT: je suis content de soulevé un débat 🙂 Supposons f,g > 0 pour des raisons de simplicité

Est-ce devoirs?
Non - seulement un pari 🙂
Aussi, pourquoi est-il clairement mauvais pour les grands-Oh?
duh - voir la question liée
Je me doute que c'est un commentaire constructif. Si ce n'est pas conforme à la FAQ le fait de la question similaire, lié et donc faire plus ou moins tout le reste tagged big-o

OriginalL'auteur Mr_and_Mrs_D | 2012-03-30

  1. 2

    Il est, au moins si g(n) est convergente vers l'infini positif pour n vers l'infini positif (si g(n) n'est-il pas facile de trouver des contre-exemples).

    Esquisse de la preuve:

    Prerequsites: g(n) est convergente vers l'infini positif pour n vers l'infini positif.

    f(n) à o(g(n)) signifie:

    for every eps > 0 exists a n0 so that for all n > n0 abs(f(n)) < abs(g(n)*eps).

    Forme de ce qui suit: 

    2^abs(f(n)) < 2^abs(g(n)*eps) = (2^eps)^g(n) (for n > n0).

    Pour eps < 1:

    (2^eps)^n is in o(2^n) (as 2^eps < 2)

    il en résulte que, pour chaque activités2 > 0 existe un n1 de sorte que, pour tous n > n1 

    (2^eps)^n < eps2*(2^n).

    Le choix des activités2 = eps vields:

    (2^eps)^n < eps*(2^n) for all n > n1 (n1 is dependent on eps)

    Parce que g(n) -> pos. inf. pour la n -> pos. inf. il existe un n2 de sorte que

    g(n) > n1 for all n > n2

    Suivantes à partir de là est 

    (2^eps)^g(n) < eps*2^g(n) for all n > n2.

    Ainsi, pour chaque 0 < eps < 1, il existe un n3 >= max(n0,n2), de sorte que 

    2^abs(f(n)) < 2^abs(g(n)*eps) = (2^eps)^g(n) < eps*2^g(n) for all n > n3.

    Pour chaque eps3 > 1:

    2^abs(f(n)) < eps*2^g(n) < eps3*2^g(n)

    Ainsi, pour chaque eps > 0, il existe un n3, de sorte que

    2^abs(f(n)) < eps*2^g(n) for all n > n3

    Becase 2^f(n) < 2^abs(f(n)) pour tout n, et 2^x > 0 pour tout réel x, il s'ensuit 

    abs(2^f(n)) < abs(eps*2^g(n)) for all n > n3

    q.e.d.

    Si quelque chose n'est pas clair ou mal, s'il vous plaît commentaire.

    EDIT: Quelques réflexions sur d'autres g(n):

    Une sous-suite de(g, n) est limité c'est à dire qu'il existe un x de sorte qu'il n'y a pas une n0 avec abs(g(n))>=x pour tout n > n0:

    o(g(n)) ne contient que des fonctions qui sont constantes 0 après un certain n ou converge vers 0. Alors 2^g(n) a également restreint de sous-suite, mais 2^f(n) est constante à 1 après un certain point.

    Il n'y a pas de n0, donc g(n) > 0 pour tout n > n0:

    2^g(n) < 1 si g(n) < 0, donc g(n) a restreint la signification o(2^g(n)) ne contient que des fonctions qui sont constantes 0 après un certain n ou converger vers 0.

    première ligne - vous dire g(n) > 0 (pour tout n après un certain point)? - c'est inutile si g->inf pour n->inf (suit). Si g(n) n'est pas (aller à l'infini) pouvez-vous le prouver ou donner un contre-exemple ? Supposons g > 0 pour tout n. Aussi votre définition est mal - o signifie que pour chaque c > 0 il existe un n0 : f < cg pour tout n=>n0 - avis de l'inégalité stricte. Supposons g,f >0.
    et qu'en eps > 1 ? également dans la ligne de (2^eps)^g(n) <= eps*2^g(n) for all n > n3. voulez-vous dire activités2 ?
    J'ai ajouté quelques croquis d'une preuve pour les autres cas, je pense (si vous pouvez penser de plus il suffit de déposer un commentaire). Oui le g(n) > 0 n'est pas vraiment nécessaire. Sur l' > vs >=: corrigé. eps > 1 n'est généralement pas un problème, si abs(f(n)) < abs(eps*g(n)) pour une eps < 1 c'est aussi pour n'importe quel eps >= 1.
    si abs(f(n)) < abs(eps*g(n)) pour une eps < 1 c'est aussi pour n'importe quel eps >= 1. : en effet, mais j'ai besoin de trouver for every eps > 0 approprié n0 s.t. f < eps*g pour n > n0 ! Votre preuve semble suggérer que si il y a un eps <1 s.t f < eps * g (un simple f = O(g), pour un bpa < 1) puis 2^f = o(2^g) - correct ?
    Aussi - sur g -> inf : pas nécessaire. Vous êtes simplement en utilisant g > 0. g peut très bien être bornée tant que f tend vers zéro, je suppose. Edit : (2^activités2)^g(n) < activités2*2^g(n) pour tout n > n3 devrait lire (2^eps)^g(n) < activités2*2^g(n) pour tout n > n3. À ce point - examen de votre question - êtes-vous vraiment en prouvant qu'un seul eps1 < 1 est-elle suffisante ?

    OriginalL'auteur Ral Zarek

  2. 1

    Voici une réponse. Le résultat dépend des propriétés de convergence de g(n).

    Tout d'abord considérer la relative limite:

    lim(x->inf) log_2 ((2^(f(n))) /(2^(g(n))))
=
lim(x->inf) ( log_2(2^(f(n))) - log_2(2^(g(n))) )
=
lim(x->inf) ( f(n) - g(n) ) = lim(x->inf) ( g(n) * f(n) /g(n) - g(n) )
=
lim(x->inf) ( -g(n) ) = - lim(x->inf) g(n)

    ... Maintenant, pour obtenir dans la forme de la question d'origine dans votre post, SI c'est mathématiquement correct pour passer à la limite et le journal (qui je le pense), alors on aurait:

    lim(x->inf) log_2 ((2^(f(n))) /(2^(g(n))))
=
log_2 lim(x->inf) ((2^(f(n))) /(2^(g(n)))).

    Maintenant, pour répondre à la question. Si il est vrai que

    2^(f(n)) = o(2^(g(n))),

    puis à la limite, la droite devient

    log_2 (0) = - inf

    ... alors dans ce cas, il doit être vrai que

    lim(x->inf) g(n) = inf

    Ce résultat ne semble pas faire sens. Envisager f(x) = exp(-x) and g(x) = 1 - exp(-x). Clairement, dans cet exemple f(x) = o(g(x)). Cependant, 2^(f(x)) is not o(2^(g(x))) parce que

    lim(x->inf) (2^exp(-x)) /(2^(1-exp(-x))) = 1/2.

    Mais étant donné f(x) = exp(x), g(x) = exp(2x), où f(x) = o(g(x)) et où lim(x->inf) g(x) = inf, réunion de la condition ci-dessus, nous avons

    lim(x->inf) (2^exp(x)) /(2^exp(2x))
=
lim(x->inf) 1 /2^(exp(x)*(exp(x) - 1)) = 0

    donc 2^(f(x)) = o(2^(g(x))).

    Je ne pense pas que l'étape de lim (g*f/g - g ) à lim -g est valable pour tous les f et g (non sans une certaine justification/explication au moins, parce que g peut aller à l'infini plus vite que f/g à zéro). Et il est bon de swap à la limite avec le journal (log est continue pour les nombres positifs, ce qui est tout ce dont vous avez besoin). Je suis d'accord avec votre conclusion (que ça dépend des propriétés spécifiques de g).
    La bonne question à soulever.
    Peut-être ce qui le prouve: Pour toute eps, cependant petit, nous avons lim f(n)/g(n) < eps pour n>N et certains N (à supposer l'ampleur de la limite est prévu). Par conséquent, lim (gf/g-g) < lim (g*eps-g) = lim (g(eps-1) = lim (-g). Pensez-vous? (Pour les dernières étapes, il suppose g>0, mais il doit être de la même forme si g<0. Peut-être il ya certains cas particulier, si g=0 dans la limite.)
    ... Addendum: il semble, en fait, que pour les dernières étapes, non seulement il est à supposer que g>0, mais il emporte aussi sur le signe de lim f/g, alors peut-être que cela influence les choses ainsi.
    Des erreurs, s'il vous plaît aller à travers elle à nouveau - pas sûr au sujet de la preuve, mais par exemple f(x) = x, g(x) = 2x, f(x) != o(g(x)) - même avec les autres. Considérons f,g positif

    OriginalL'auteur Dan Nissenbaum

  3. -1

    Facile la Preuve avec un exemple,

    Si f(n) = O(g(n)),
    2^(f(n)) n'est pas égale à O(2^g(n)))

    Laisser, f(n) = 2log n et
    g(n) = log n

    (À supposer journal est à la base 2)

    Nous le savons, 2log n <= c(log n)
    donc f(n) = O(g(n))

    2^(f(n)) = 2^n log^2 = n^2

    2^(g(n)) = 2^log n = n

    Nous savons qu'

    n^2 n'est pas en O(n)

    Par conséquent, 2^(f(n)) n'est pas égale à O(2^g(n)))

    C'est big-O - question est à propos de little-o....

    OriginalL'auteur Mohit Arvind khakharia