Beziehung von Funktion zeigen. Behauptung: Für f(n) = 3n^2 + n + 17 gilt f(n) ∈ Θ(n^2) .

Question

Hallo ihr lieben. 

Ich hoffe ihr könnt mir bei dieser Aufgabe helfen, bei der ich keine Ansätze/Lösungen finde.

Zeigen , dass für die Funktion f(n) = 3n2 + n + 17 die Beziehung f(n) ∈ Θ(n2) gilt. 

Benutzen Sie die Definition von Θ(g(n)). Zeigen Sie die Existenz der Konstanten exakt! 

Answer 1

Hi,

es gilt:

$$f(n) \in \theta (g(n)) \ \Leftrightarrow \exists N \in \mathbb{N} \ \exists c>0  \ \forall n \ge N: \ f(n)=O(g(n)) \ \land \ f(n)=\Omega(g(n))$$

Hierbei ist

$$f(n)=O(g(n)) \Leftrightarrow \exists N \in \mathbb{N} \ \exists c_1>0  \ \forall n \ge N: f(n) \le g(n) \cdot c_1 $$

und

$$f(n)=\Omega(g(n)) \Leftrightarrow \exists N \in \mathbb{N} \ \exists c_2>0  \ \forall n \ge N: f(n) \ge g(n) \cdot c_2 $$

Fangen wir mit f(n)=O(g(n)) an:Es gilt$$f(n) \le g(n) \cdot c_1 \Leftrightarrow \frac{f(n)}{g(n)} \le c_1$$In unserem Fall ist f(n)=3n²+n+17 und g(n)=n².D.h. wir müssen zeigen, dass$$ \frac{3n^2+n+17}{n^2} \le c_1$$ist für ein c₁>0.Welche c₁ kommen in Frage?