Theta-Notation: n⋅log n in Θ(n3)?

Question

ich habe eine kurze Frage und zwar liegt $n\cdot \log(n)$ wirklich in $\Theta(n^3)$?
Und wenn ja, warum?

Und was ist wenn wir $n\cdot \log(n^4)$ haben? In welcher Theta-Notation liegt diese dann?

Answer 1

Hallo :-)

Ich glaube du meinst $n\cdot \log(n)\in \Theta(n^3)$. Um das zu zeigen, musst du zeigen:

1.) $n\cdot \log(n)\in \Omega(n^3)$ und

2.) $n\cdot \log(n)\in \mathcal{O}(n^3)$

Aussage 1.) ist aber falsch und Aussage 2.) ist richtig, sodass nur $n\cdot \log(n)\in \mathcal{O}(n^3)$ gilt und $n\cdot \log(n)\notin \Omega(n^3)$, sodass auch $n\cdot \log(n)\notin \mathcal{O}(n^3)\cap \Omega(n^3) = \Theta(n^3)$.

Für $n\cdot \log(n^4)=4\cdot n\cdot \log(n)$ zählt genau dasselbe, wie oben.

Comments

Oh, jetzt ist mir einiges klar. Ich Danke Dir für die ausführliche und schöne Erklärung! :-D

---

Eine Frage habe ich noch:
Wie zeigt man sowas eigentlich bzw. rechnet denn da? Mit Master-Theorem?

Zum Beispiel habe ich diese Aufgabe hier gegeben, aber ich weiß leider nicht wie man das hier genau beweisen kann:

---

Da musst du auch nur wieder die Definitionen nachprüfen:

Es sei $g: \mathbb{N}\rightarrow \mathbb{R}$.

$$1.)\quad \mathcal{O}(g):=\{f:\ \mathbb{N}\rightarrow \mathbb{R}:\ \exists \alpha>0 \ \exists n_0 \in \mathbb{N} \ \forall n\geq n_0:\ \underbrace{0\leq f(n) \leq \alpha \cdot g(n)}_{0\leq f(n) \text{ und } f(n)\leq \alpha\cdot g(n) } \}$$

$$2.)\quad \Omega(g):=\{f:\ \mathbb{N}\rightarrow \mathbb{R}:\ \exists \beta>0 \ \exists n_1 \in \mathbb{N} \ \forall n\geq n_1:\ \underbrace{0\leq \beta \cdot g(n) \leq f(n)}_{0\leq \beta\cdot g(n) \text{ und } \beta\cdot g(n)\leq f(n) } \}$$

$$3.)\quad \Theta(g):=\mathcal{O}(g)\cap \Omega(g)$$

Zu 1.). Finde also ein $\alpha>0$ und eine Stelle $n_0\in\mathbb{N}$, sodass für alle $n\geq n_0$ die Ungleichung $0\leq n\cdot \log_3(n^2)\leq \alpha\cdot n\cdot (\log_3(n))^2$ gilt. Diese Parameter kann man beim bloßen Versuch der Abschätzung einsehen:

$0\stackrel{n\geq 1}{\leq} \log_3(n)$

Daraus folgt

$$0\stackrel{n\geq 1}{\leq} n\cdot \log_3(n^2)=2\cdot n\cdot \underbrace{\log_3(n)}_{\geq 1,\space \forall n\geq 3}\stackrel{n\geq 3}{\leq }2\cdot n\cdot \log_3(n)\cdot \log_3(n)=2\cdot n\cdot (\log_3(n))^2$$

Also gilt mit $\alpha=2$ und $n_0=3$ für alle $n\geq 3$ die Abschätzung

$0\leq n\cdot \log_3(n^2)\leq \alpha\cdot n\cdot (\log_3(n))^2$,

sodass $n\cdot \log_3(n^2)\in \mathcal{O}(n\cdot (\log_3(n))^2)$ gilt.

Zu 2.). Diese Aussage ist falsch. Um das zu zeigen, muss man also die Aussage

$n\cdot \log_3(n^2)\notin \Omega(n\cdot (\log_3(n))^2)$ betrachten. In Quantorenschreibweise sieht das so aus:

$$\forall \beta>0 \ \forall n_1 \in \mathbb{N} \ \exists n\geq n_1:\ \underbrace{0> \beta\cdot n\cdot (\log_3(n))^2}_{(1)} \text{ oder } \underbrace{\beta\cdot n\cdot (\log_3(n))^2> n\cdot \log_3(n^2)}_{(2)}$$

(1) ist offensichtlich immer falsch.

Also muss man (2) zeigen, sodass diese Oder-Aussage wahr ist. Finde also in Abhängigkeit von $\beta>0$ und $n_0\in \mathbb{N}$ ein $n\geq n_0$, sodass Abschätzung (2) gilt.

Dafür probiert man etwas rum:

$\beta\cdot n\cdot (\log_3(n))^2> n\cdot \log_3(n^2)$.

Zu kompliziert. Ich betrachte stattdessen:

$\beta\cdot (\log_3(n))^2> \log_3(n^2)=2\cdot \log_3(n)$.

Immernoch zu kompliziert. Also:

$\beta\cdot \log_3(n)> 2$  bzw. $\log_3(n)>\frac{2}{\beta}$   bzw.  $n>3^{\frac{2}{\beta}}$

Das letzte sieht sehr vielversprechend aus. Um jetzt noch $\beta>0$ und $n_0\in \mathbb{N}$ ins Boot zu holen, wähle ich mein finales $n\in \mathbb{N}$ folgendermaßen:

$n>\max\left(\beta, n_0,3^{\frac{2}{\beta}}\right)$. Dann ist $n>n_0$ und $n>3^{\frac{2}{\beta}}$. Also hat man:

$$\begin{aligned}n&>3^{\frac{2}{\beta}}>1\\[10pt]&\Leftrightarrow \log_3(n)>\frac{2}{\beta}\\[10pt]&\Leftrightarrow \beta\cdot \log_3(n)>2\\[10pt]&\Leftrightarrow \beta\cdot (\log_3(n))^2>2\cdot \log_3(n)\\[10pt]&\Leftrightarrow \beta\cdot n\cdot (\log_3(n))^2>2\cdot n\cdot \log_3(n)=n\cdot \log_3(n^2)\end{aligned}.$$

Also hat man damit $n\cdot \log_3(n^2)\notin \Omega(n\cdot (\log_3(n))^2)$ gezeigt.

Insgesamt gilt also $n\cdot \log_3(n^2)\notin \Theta(n\cdot (\log_3(n))^2)$.