Naja, eine Konstante ist 1, und für n >= 4 gilt
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)
Being smart will count for nothing if you don't make the world better. You have to use your smarts to count for something, to serve life, not death.