Zwei Behauptungen zur O-Notation

Question

Aufgabe:

\( \sqrt{n} \in O(n) \)
\( n^{3} \in O\left(\sum \limits_{i=0}^{n} i\right) \)

Problem/Ansatz:

Hallo,

die obigen Aussagen müssen mit der lim Definition der O-Notation bewiesen bzw. widerlegt werden.

Answer 1

Aloha :)

$$\lim\limits_{n\to\infty}\frac{\sqrt n}{n}=\lim\limits_{n\to\infty}\frac{1}{\sqrt n}=0<\infty\quad\implies\quad \sqrt n\in O(n)$$

Für die zweite Teilaufgabe kannst du dir überlegen, dass:$$O\left(\sum\limits_{i=0}^n i\right)=O\left(\frac{n^2+n}{2}\right)=O(n^2)$$Da \(n^3\) schneller wächst als alle Funktionen in \(O(n^2)\), gilt:\(\quad n^3\not\in O\left(\sum\limits_{i=0}^n i\right)\)

Comments

Hallo und danke für die Antwort,

ich wollte noch kurz wissen, wieso O((n^2+n)/2) = O(n^2) ist?

---

$$\lim\limits_{n\to\infty}\frac{\frac{n^2+n}{2}}{n^2}=\lim\limits_{n\to\infty}\left(\frac12+\frac{1}{2n}\right)=\frac12<\infty\implies O\left(\frac{n^2+n}{2}\right)\in O(n^2)$$$$\lim\limits_{n\to\infty}\frac{n^2}{\frac{n^2+n}{2}}=\lim\limits_{n\to\infty}\frac{2}{1+\frac1n}=2<\infty\implies O(n^2)\in O\left(\frac{n^2+n}{2}\right)$$$$\leadsto O\left(\frac{n^2+n}{2}\right)=O(n^2)$$

---

Hallo,

nochmal eine kurze Frage, wie bist du in den ersten beiden Zeilen auf die ersten Umformungen gekommen?

mfg

ulong

---

Oha, manchmal mache ich ein paar viele Umformungsschritte im Kopf... sorry.

$$\frac{\frac{n^2+n}{2}}{n^2}=\frac{1}{n^2}\cdot\frac{n^2+n}{2}=\frac{1}{n^2}\left(\frac{n^2}{2}+\frac{n}{2}\right)=\frac{1}{2}+\frac{1}{2n}$$$$\frac{n^2}{\frac{n^2+n}{2}}=\frac{n^2}{\frac{n^2}{2}+\frac{n}{2}}=\frac{n^2}{n^2\left(\frac{1}{2}+\frac{1}{2n}\right)}=\frac{1}{\frac12+\frac{1}{2n}}=\frac{2}{1+\frac1n}$$