Est 2^(2n) = O(2^n)

Est 2(n+1) = O(2n)?

Je crois que c'est correct parce que n+1 ~= n.

Est 2(2n) = O(2n)?

Celui-ci semble comme il l'aurait fait d'utiliser la même logique, mais je ne suis pas sûr.

InformationsquelleAutor JustinY17 | 2011-01-31
  1. 4

    Noter que 

    2n+1 = 2(2n)

    et 

    22 = (2n)2

    À partir de là, soit utiliser les règles de Big-O de notation que vous savez, ou utiliser la définition.

    • Alors, qu'est-ce que le Big-o pour 2^2n?
    • 2^2n = (2^2)^n = O(4^n)
    • Quels sont les noms réels de ces deux?
    InformationsquelleAutor BlueRaja - Danny Pflughoeft
  2. 11

    Premier cas, c'est évidemment vrai - que vous venez de tenir à l'écart de la constante

    Actuel réponses à la deuxième partie de la question, ressembler à un handwaving pour moi, donc je vais essayer de donner un bon mathématiques explication. Supposons que la deuxième partie est vraie, puis, à partir de la définition de big-O, vous avez:

    Est 2^(2n) = O(2^n)

    qui est manifestement erronée, car il n'existe pas de constante que de répondre à ces inégalités.

    • Doit être accepté de répondre.
    InformationsquelleAutor Salvador Dali
  3. 4

    Je suis en supposant que vous avez juste à gauche hors de la O() notation sur le côté gauche.

    O(2^(n+1)) est le même que O(2 * 2^n), et vous pouvez toujours sortir des facteurs constants, de sorte qu'il est le même que O(2^n).

    Cependant, des facteurs constants sont la seule chose que vous pouvez tirer. 2^(2n) peut être exprimé en tant que (2^n)(2^n), et 2^n n'est pas une constante. Donc, la réponse à votre question est oui et non.

    • 2^(n+1) = O(2^n) est commun, incroyablement malheureux notation pour dire "L'ordre de 2^(n+1) est Big-O (2^n)" Si j'ai eu mon chemin, au lieu de cette terrible S, Ω, Θ notation, nous utiliserions un symbole de Θ en conjonction avec ≤, ≥, et = pour spécifier l'ordre; la déclaration ci-dessus serait alors être écrite comme Θ(2^(n+1)) ≤ Θ(2^n). Malheureusement, ce n'est tout simplement pas la façon dont il fonctionne 🙁
    InformationsquelleAutor David Thornley
  4. 4

    Demande: 2^(2n) != O(2^n)

    La preuve par contradiction:

    1. Assumer: 2^(2n) = O(2^n)
    2. Ce qui signifie, il existe c>0 et n_0 s.t. 2^(2n) <= c * 2^n pour tout n >= n_0
    3. Divisant les deux côtés par 2^n, nous obtenons: 2^n <= c * 1
    4. Contradiction! 2^n n'est pas bornée par une constante c.

    Donc 2^(2n) != O(2^n)

    InformationsquelleAutor shisui
  5. 2

    Pour répondre à ces questions, vous devez payer une attention particulière à la définition de big-O de notation. Vous devez donc vous demander:

    est-il une constante C telle que 2^(n+1) <= C(2^n) (à condition que n est assez grand)?

    Et il en va de même pour l'autre exemple: est-il une constante C telle que 2^(2n) <= C(2^n) pour tout n qui est assez grand?

    De travail sur les inégalités et vous serez sur votre chemin vers la solution.

    InformationsquelleAutor Jong Bor Lee
  6. 1

    2n+1 = O(2n) car 2n+1 = 21 * 2n = O(2n).
    Supposons que 22 = O(2n), Alors il existe une constante c telle que pour n au-delà de certains n0, 22 <= c 2n. En divisant les deux côtés par 2n, nous obtenons 2n <. c. Il n'y a pas de valeurs de c et de n0 que peut faire ce vrai, donc l'hypothèse est fausse et 22 != O(2n)

    InformationsquelleAutor Pianistprogrammer