# Groß-O-Notation



## fornicator (20. Aug 2011)

Hallo zusammen,
habe folgende Aufgaben: Beweisen oder wiederlegen sie 
1)f(n)=2^(n+1)      - Ist f(n) Element von O(2^n)
Nein, denn f(n) ist immer größer. 2^(n+1)>2^n -> 2>1 
2)f(n)=2^(2n)     - Ist f(n) Element von O(2^n)
Nein, denn f(n) ist immer größer 2^(2n)>2^n  -> 2^n > 1 (Das 2^n > 1 spar ich mir zu beweisen)
3)f(n)=(n+a)^3  - Ist f(n) Element von diesem O mit dem Strich drinnen(n^3)
f(n)=n^3+3n^2a+3na^2+a^3  -> Für große Eingaben ist nur der größte Exponent wichtig 
   -> für große n gilt also näherungsweise f(n)=n^3  ->  f(n) ist Element von dem O mit dem Strich drinnen

Stimmt das so? - Und dan noch eine Zusatzfrage: Kennt einer von euch eine gute Seite/Buch das hauptsächlich aus Übungsaufgaben (am besten mit Lösungen)zu Algorithmen beseteht?(Laufzeitermittlung, O-Notation..)


----------



## xehpuk (20. Aug 2011)

Bin da auch nicht so fit drin, ich würds aber so sagen:


fornicator hat gesagt.:


> 1)f(n)=2^(n+1) - Ist f(n) Element von O(2^n)
> Nein, denn f(n) ist immer größer. 2^(n+1)>2^n -> 2>1


Aussage stimmt: 2^(n+1) = 2*2^n = O(2^n)



fornicator hat gesagt.:


> 2)f(n)=2^(2n) - Ist f(n) Element von O(2^n)
> Nein, denn f(n) ist immer größer 2^(2n)>2^n -> 2^n > 1 (Das 2^n > 1 spar ich mir zu beweisen)


Aussage stimmt nicht: 2^(2n) = (2^2)^n = 4^n = O(4^n)


----------



## fornicator (20. Aug 2011)

> Aussage stimmt: 2^(n+1) = 2*2^n = O(2^n)


Hm wie kommst du dadrauf? Weil das 0 heißt doch das es kleiner sein soll. Also das man schauen muss ob gilt : 2^(n+1)>2^n  
Deine Antwort würde zu dem O mit dem Strich drinnen passen, oder hab ich da was verauscht?


----------



## XHelp (20. Aug 2011)

Zu dem Theta würde es nicht passen, denn Theta heißt "genau so schnell".
Bei der O-Notation kannst du nicht einfach sagen: die Zahlen sehen irgendwie größer aus, also könnte das stimmen, da gibt es eine formale Beschreibung (siehe z.B. wikipedia), wodurch ersichtlich wird, dass Konstanten keine Rolle spielen


----------



## Firephoenix (20. Aug 2011)

Hi,
Konstanten nicht, die Basis bei der Exponentialrechnung ist aber keine Konstante.
und da 2^2n = 4^n und 4^n ist nicht in O(2^n).

Anders sieht das bei 2^(n+1) in O(2^n) aus, das ergibt wie xehpuk richtig umgeformt hat
2*2^n und hier ist 2 eine konstante die man rauswerfen kann, deswegen ist
2^(n+1) in O(2^n)
Gruß


----------

