0 Daumen
1,4k Aufrufe

F4A92BB1-CF32-4E90-98F0-9B13ACFFAB1B.jpeg

Text erkannt:

Beispiel 1.4.
(a) \( \log _{2} n=\mathcal{O}(n) \)
(b) \( 2^{100}=\mathcal{O}(1) \)
(c) \( n \log _{2} n=\mathcal{O}\left(\frac{n}{2} \log _{2} \frac{n}{2}\right) \)
(d) \( \frac{n}{5}=\mathcal{O}\left(\frac{1}{n}\right) \)
(e) \( \log _{2}\left(2 n^{2}\right)=\mathcal{O}\left(\log _{2} n\right) \)

Kann mir jemand bitte erklären wie ich diese Aussagen beweisen soll?

Avatar von

1 Antwort

0 Daumen
 
Beste Antwort

Aloha :)

Es gibt zwei Möglichkeiten zu zeigen, dass \(f\in O(g)\) ist.

1) Du findest eine positive Konstante \(c>0\) und ein \(n_0\in\mathbb N\), sodass gilt:$$f(n)\le c\cdot g(n)\quad\text{für } n\ge n_0$$

2) Du zeigst, dass der folgende Grenzwert exisitert:$$\lim\limits_{n\to\infty}\left|\frac{f(n)}{g(n)}\right|<\infty$$

zu a) richtig, denn:$$e^x\ge1+x\implies e^n\ge1+n>n\implies n>\ln(n)\implies\frac{n}{\ln2}>\log_2(n)$$Es gibt also eine Konstante \(c=\frac{1}{\ln2}\), sodass für alle \(n\in\mathbb N\) gilt: \(\log_2(n)<c\cdot n\).

zu b) richtig, denn mit \(c=2^{100}\) gilt für alle \(n\in\mathbb N\):$$2^{100}\le c\cdot 1$$

zu c) richtig, denn für \(n\ge n_0=4\) gilt:$$n(n-4)\ge0\implies n^2-4n\ge0\implies n^2\ge4n\implies\left(\frac{n}{2}\right)^2\ge n\implies$$$$\log_2(n)\le\log_n\left(\left(\frac{n}{2}\right)^2\right)=2\log_n\left(\frac{n}{2}\right)\implies n\log_2(n)\le2n\log_2\left(\frac{n}{2}\right)\implies$$$$n\log_2(n)\le4\cdot\frac{n}{2}\log_2\left(\frac{n}{2}\right)$$Mit \(c=4\) und \(n_0=4\) folgt die Behauptung.

zu d) falsch, denn:$$\lim\limits_{n\to\infty}\left|\frac{\frac{n}{5}}{\frac{1}{n}}\right|=\lim\limits_{n\to\infty}\left|\frac{n^2}{5}\right|=\infty$$

zu e) falsch, denn für \(n\ge2\) gilt:$$\lim\limits_{n\to\infty}\left|\frac{2n^2}{\log_2(n)}\right|\ge\lim\limits_{n\to\infty}\left|2n\right|=\infty$$

Avatar von 148 k 🚀

Vielen Dank lieber Tschakabumba!

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community