Konstante für Komplexitätsklasse finden

[Angel4585]

Hallöchen

Ich bereite mich grad auf meine Klausuren vor und arbeite die alten Klausuren durch bei denen ich ein Problem bei einer Aufgabe habe.

Wir sollen beweisen, dass etwas innerhalb einer bestimmten Komplexität liegt indem wir eine Konstante berechnen, also z.B.:

3n² + 2n + 5 = O(n²)
3n² + 2n + 5 <= 3n² + 2n² + 5n²
3n² + 2n + 5 <= 10n²

=> Die gesuchte Konstante ist 10.

Die Aufgabe bei der ich Probleme habe ist folgende:

n² = O(2^n) (also 2 hoch n)

Ich hab keinen Plan wie ich da anfange

Kann mir da jemand auf die Sprünge helfen?

[s.h.a.r.k]

Kannst du deinem Thread mal einen Aussagekräftigen Titel geben?! Wäre nett, danke

Ich würde hier so anfangen:

n^2 = O(2^n)
n^2 <= a*2^n

So kommst ja auf die Konstante. Soweit ich das noch weiß geht es ja darum, dass du eine Konstante findest, aber der das eben gilt, oder? Dann dürfte der Ansatz doch passen!?

[Gausi]

Naja, eine Konstante ist 1, und für n >= 4 gilt

Code:

n^2 <= 2^n

Das würde ich einfach per Induktion zeigen. Der Induktionsanfang ist klar: 4^2=16 und 2^4=16, stimmt also.

Induktionsschritt n -> n+1:

Code:

   (n+1)^2 
=  n^2 + 2n + 1 
<= n^2 + 2n + 2n    (n >= 4)
=  n^2 + 4n 
<= n^2 + n^2        (n >= 4)
<= 2 * 2^n          (Induktionsvoraussetzung)
=  2^(n+1)

Somit liegt n^2 in O(2^n)

[gammatester]

n^2 is doch wohl o(2^n). Also kannst Du jeden beliebigen positiven Wert > 0 nehmen.