0 Daumen
588 Aufrufe

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! 

Avatar von

1 Antwort

+1 Daumen

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)=3n2+n+17 und g(n)=n2.D.h. wir müssen zeigen, dass$$ \frac{3n^2+n+17}{n^2} \le c_1$$ist für ein c1>0.Welche c1 kommen in Frage?
Avatar von 2,9 k

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community