Wie könnte man das mit der Limes-Definition von groß O beweisen?

Question

\( f(n) \in O\left(n^{2}\right) \) mit \( f(n)=\left\{\begin{array}{ll}n^{2} & \text { falls } n \text { gerade } \\ n & \text { falls } n \text { ungerade }\end{array}\right. \)

Wie könnte man das mit der Limes-Definition von groß O beweisen ?

Comments

Hier ist \(f(n)\) sogar in \(O(n)\), weil jeder Programmierer bei einer geraden Anzahl \(n\) von Objekten ein Dummy-Objekt dabei packen würde, um die lineare Laufzeit zu erhalten ;)

Answer 1

Für alle \(n\in \mathbb{N}\) ist \(|f(n)|\leq |n^2|\), also

        \(\left|\frac{f(n)}{n^2}\right| \leq 1\).

Somit ist auch

        \(\limsup_{n\to \infty} \left|\frac{f(n)}{n^2}\right| \leq 1\).