O Notation 2^2n €O (2^n)?

1 Antwort

Nein.

Du hast 2^(2n) = 2^n * 2^n, also für alle c > 0:

2^(2n) <= c * 2^n, nur wenn 2^n <= c, äquivalent zu n <= log(c).

Also existiert für alle c ein n, sodass 2^(2n) > c * 2^n, also 2^(2n) nicht in O(2^n).

LG


FredBAM 
Fragesteller
 22.03.2018, 19:50

Danke :) deine Erklärung war auch passend! :)

0
Roach5  27.03.2018, 04:15

Eine kleine Anmerkung: "Es existiert für alle c ein n, sodass 2^(2n) > c*2^n" ist nicht genug um "2^(2n) nicht in O(2^n)" zu zeigen. Was wir gezeigt haben ist, dass es unendlich viele (sprich: ein beliebig großes) solche n gibt, das ist das wichtige! Entschuldige, dass ich mich hier verschrieben habe.

0