Konstante für Komplexitätsklasse finden

[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)