Groß-O-Notation

[fornicator]

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]

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

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)

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]

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]

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]

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ß