O-Notation Aufgabe Beweis für f1, f2 ∈ O(n)

Question

Aufgabe:

Gegeben sind die Funktionen f1, f2 ∈ O(n).

Beweisen oder widerlegen Sie: f1 ∉ O(f2) ⇒ f2 ∈ O(f1)

Problem/Ansatz:

Könnte mir jemand weiterhelfen, wie ich das lösen soll. Danke

Answer 1

Da du keine weiteren Voraussetzungen spezifiziert hast, wähle z.B.

$$f_1(n)=\begin{cases} 1, \ n \text{ gerade} \\ n, \ n \text{ ungerade} \end{cases}, \ f_2(n)=\sqrt{n}$$

und zeige den Widerspruch.