Big O für logarithmische Funktion beweisen

Question

Servus!

Im Moment beschäftigen wir uns mit Komplexitätsanalysen und ich soll beweisen, dass

für \( f(n)=5n^2+3n\log_{2}{n}+2n+5\\ f(n)\in O(n^2) \) gilt.

Problem/Ansatz:

Ich würde das ganze über vollständige Induktion lösen aber dabei gelingt es mit nicht \( \log_{2}{(n+1)} \) aufzulösen (Bin mittlerweile leider mathematisch etwas eingerostet). Die restlichen Aufgaben sind sehr ähnlich daher wäre es eine große Hilfe einmal zu sehen, wie das bei dieser Aufgabe geht.

Danke!

Answer 1

Hallo :-)

Ich schreibe mal die ,,übliche" Landau-Definition für groß-O hin:$$ \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) \ \land f(n)\leq \alpha\cdot g(n) }  \} $$Du musst also eine Konstante \(\alpha>0\) und eine Stelle \(n_0 \in \mathbb{N}\) finden, sodass für alle \( n\geq n_0\) die Ungleichung \(0\leq f(n)\leq \alpha\cdot g(n)\) gilt.

Es ist  \( f(n)=5n^2+3n\log_{2}(n)+2n+5 \in \mathcal{O}(n^2) \) zu zeigen.

Ich suche also eine Konstante \(\alpha>0\) und eine Stelle \(n_0 \in \mathbb{N}\), sodass für alle \( n\geq n_0\) die Ungleichung \(0\leq \underbrace{5n^2+3n\log_{2}(n)+2n+5}_{=f(n)}\leq \alpha\cdot \underbrace{n^2}_{=g(n)}\) gilt.

Entweder man sieht bereits, welche Konstante \(\alpha>0\) und Stelle \(n_0\in \mathbb{N}\) zu verwenden sind, denn dann kannst du mit Induktion die Ungleichung zeigen. Oder man bekommt diese durch geschicktes Abschätzen mitgeliefert. Ich wähle letzteres:

$$  \begin{aligned}0&\stackrel{n\geq 1}{\leq} 5n^2+3n\log_{2}(n)+2n+5\\&= 5n^2+(n\log_{2}(n)+n\log_{2}(n)+n\log_{2}(n))+2n+5\\&\stackrel{n\geq \log_2(n), n\geq 1}{\leq} 5n^2+(n\cdot n+n\cdot n+n\cdot n)+2n+5\\&=8n^2+2n+5\\&\leq 8n^2+2n^2+5n^2=15\cdot n^2\end{aligned} $$

Also wähle ich \(\alpha=15\) und \(n_0=1\).

Damit ist \(5n^2+3n\log_{2}(n)+2n+5\in \mathcal{O}(n^2)\).

Answer 2

Aloha :)

Du brauchst nur zu zeigen, dass der folgende Grenzwert exisitert:$$\left|\frac{f(n)}{n^2}\right|=\frac{5n^2+3n\log_2(n)+2n+5}{n^2}=5+\frac{3\log_2(n)}{n}+\frac2n+\frac{5}{n^2}\to5<\infty\quad\checkmark$$Daher ist \(f(n)\in O(n^2)\).

Für praktische Rechnungen ist die Ungleichung \(\ln(x)<\sqrt x\) oft sehr nützlich. Auch hier:$$\frac{3\log_2(n)}{n}=\frac{3\frac{\ln(n)}{\ln(2)}}{n}=\frac{3}{\ln(2)}\cdot\frac{\ln(n)}{n}<\frac{3}{\ln(2)}\cdot\frac{\sqrt n}{n}=\frac{3}{\ln(2)}\cdot\frac{1}{\sqrt n}\to0$$

Comments

Hallo Tschakabumba,

Wie heißt die Regel/Formel für log₂ (n)=ln(n)/ln(2)? Ich habe die noch nie gesehen

VG aki57

---

Oha, das ist eine recht wichtige Beziehung. Du kannst den Logarithmus zu einer beliebigen Basis \(b\) immer mit dem natürlichen Logarithmus ausdrücken:$$\log_b(x)=\frac{\ln(x)}{\ln(b)}$$

Das kannst du dir wie folgt klarmachen:$$\left.b^{\log_b(x)}=x=e^{\ln(x)}\quad\right|\ln(\cdots)$$$$\left.\ln\left(b^{\log_b(x)}\right)=\ln\left(e^{\ln(x)}\right)\quad\right|\ln(a^b)=b\ln(a)$$$$\left.\log_b(x)\cdot\ln(b)=\ln(x)\cdot\underbrace{\ln(e)}_{=1}\quad\right|\colon\ln(b)$$$$\log_b(x)=\frac{\ln(x)}{\ln(b)}$$

Ich habe das damals als "Basiswechsel" kennen gelernt:

https://www.mathebibel.de/logarithmusgesetze#basiswechsel

---

Vielen Dank, sehr nett von dir.