O Notation 2^2n €O (2^n)?
ja hey :)
ist diese Aussage korrekt?
22n €O(2n)
Dankeschön :)
1 Antwort
Nutzer, der sehr aktiv auf gutefrage ist
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
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.