Aufgabe mit Lösung O-Notation (Landau-Symbol)

Die Aussage \( 42n + 8 ~\in~ \mathcal{O}(n) \) ist wahr, denn mit \( g(n) = 42n \) und \(f(n) = n \) folgt nach der Definition des O-Symbols (siehe Hinweis):1\[ 42n + 8 ~\leq~ c_1 \, n + c_2 \]mit \(c_1 ~\geq~ 42, c_2 ~\geq~ 8\).

Mit \( g(n) = 3^n \) und \(f(n) = n \) folgt nach der Definition des O-Symbols:2\[ 3^n ~\stackrel{?}{\leq}~ 2^{c_1 \, n + c_2} \]3\[ e^{\ln(3)\,n} ~\stackrel{?}{\leq}~ e^{\ln(2)\, (c_1 \, n + c_2)} \]4\[ \ln(3)\,n ~\leq~ \ln(2)\, (c_1 \, n + c_2) \]

Für \(c_1 ~\geq~ \ln(3) / \ln(2) \) ist 2 erfüllt und damit \( 3^n \in 2^{\mathcal{O}(n)} \) wahr.

Mit \( g(n) = 5n^3 \) und \(f(n) = n \) folgt nach der Definition des O-Symbols:5\[ 5n^3 ~\stackrel{?}{\leq}~ 2^{c_1 \, n + c_2} \]6\[ 5n^3 ~\stackrel{?}{\leq}~ e^{\ln(2)\, (c_1 \, n + c_2)} \]

Vergleich der dritten Ableitungen (Regel von de l’Hospital) von 6:7\[ 30 ~\leq~ e^{\ln(2)\, (c_1 \, n + c_2)} \, (\ln(2)\, c_1)^3 \]

Da 7 erfüllt ist, ist \( 5n^3 \in 2^{\mathcal{O}(n)} \) wahr.

Mit \( g(n) = n\,\log_2(n) \) und \(f(n) = n^2 \) folgt nach der Definition des O-Symbols:8\[ n\,\log_2(n) ~\stackrel{?}{\leq}~ c_1 \, n^2 + c_2 \]

Teile auf beiden Seiten durch \(n\):9\[ \log_2(n) ~\stackrel{?}{\leq}~ c_1 \, n + \frac{c_2}{n} \]

Gleichung 9 ist erfüllt, falls folgende Gleichung erfüllt ist (denn \(\frac{c_2}{n} \geq 0 \)):10\[ \log_2(n) ~\stackrel{?}{\leq}~ c_1 \, n \]11\[ n ~\stackrel{?}{\leq}~ 2^{c_1 \, n} \]

Da 11 erfüllt ist, ist \( n\,\log_2(n) \in \mathcal{O}(n^2) \) wahr.

Mit \( g(n) = n^4 \) und \(f(n) = n^3\,\log_2(n) \) folgt nach der Definition des O-Symbols:12\[ n^4 ~\stackrel{?}{\leq}~ c_1 \, n^3\,\log_2(n) + c_2 \]

Teile 12 auf beiden Seiten durch \(n^4\):13\[ 1 ~\stackrel{?}{\leq}~ c_1 \, \frac{1}{n}\,\log_2(n) + \frac{c_2}{n^4} \]

Für große \(n\) geht \(c_2/n^4\) gegen Null und kann bei großen \(n\) vernachlässigt werden:14\[ 1 ~\stackrel{?}{\leq}~ c_1 \, \frac{1}{n}\,\log_2(n) \]

Rechne auf beiden Seiten \(2^x\):15\[ 2 ~\stackrel{?}{\leq}~ 2^{\frac{c_1 \, \log_2(n)}{n}} \]16\[ 2 ~\stackrel{?}{\leq}~ \left(2^{\log_2(n)}\right)^{\frac{c_1}{n}} \]17\[ 2 ~\not\leq~ n^{\frac{c_1}{n}} \]

Ungleichung 17 ist für große \(n\) nicht erfüllt, denn der Exponent auf der rechten Seite geht gegen 0. Damit ist der Grenzwert auf der rechten Seite \(n^0 = 1 \). Es gibt also keine Konstante \(c_1\), sodass ab einem festen \(n\) die Ungleichung immer erfüllt wäre. Folglich ist \( n^4 \not\in \mathcal{O}(n^3\,\log_2(n)) \) wahr.

Mit \( g(n) = 6\,n^4 + 7n^3 + 18 \) und \(f(n) = n^5 \) folgt nach der Definition des \(\mathcal{O}\)-Symbols:18\[ 6\,n^4 + 7n^3 + 18 ~\stackrel{?}{\leq}~ c_1 \,n^5 + c_2 \]

Teile auf beiden Seiten durch \(n^4\)19\[ 6 + \frac{7}{n} + \frac{18}{n^4} ~\leq~ c_1 \,n + \frac{c_2}{n^4} \]

Jeder Summand, in dem \(n\) im Nenner steht, geht im Gegensatz zum linearen Term \( c_1 \,n \) gegen Null. Folglich existieren Konstanten \(c_1, c_2\) für die die Ungleichung 19 erfüllt ist. Damit ist \(6\,n^4 + 7n^3 + 18 \in \mathcal{O}(n^5)\).

Mit \( g(n) = n \, \log_2(n) + n^2 \, \sqrt{n} \) und \(f(n) = n^4 \) folgt nach der Definition des \(\mathcal{O}\)-Symbols:20\[ n \, \log_2(n) + n^2 \, \sqrt{n} ~\stackrel{?}{\leq}~ c_1 \, n^4 + c_2 \]

Teile auf beiden Seiten durch \(n\):21\[ \log_2(n) + n \, \sqrt{n} ~\stackrel{?}{\leq}~ c_1 \, n^3 + \frac{c_2}{n} \]

Ungleichung 21 ist erfüllt, falls folgende Ungleichung erfüllt ist (da \(\frac{c_2}{n} \geq 1 \)):22\[ \log_2(n) + n \, \sqrt{n} ~\stackrel{?}{\leq}~ c_1 \, n^3 \]23\[ \log_2(n) ~\stackrel{?}{\leq}~ c_1 \, n^3 - n \, \sqrt{n} \]

Wende auf beiden Seiten \(2^x\) an:24\[ n ~\stackrel{?}{\leq}~ 2^{ c_1 \, n^3 - n \, \sqrt{n} } = 2^{ n \, (c_1 \, n^2 - \sqrt{n})} \]

Ungleichung 24 ist erfüllt, falls folgende Ungleichung erfüllt ist (da \(c_1 \, n^3 - n \, \sqrt{n} \geq 0 \)):25\[ n \leq 2^n \]

25 ist erfüllt, deshalb ist \(n \, \log_2(n) + n^2 \, \sqrt{n}\) in der Menge \(\mathcal{O}(n^4)\).