Wachstum von Algorithmen

Question

Aufgabe:

a) $\ln (n)+1=O(\sqrt{n})$
b) $\left(\begin{array}{l}n \\ 2\end{array}\right)=O\left(n^{2}\right)$
c) $2^{n+1}=O\left(2^{n}\right)$
d) $3^{2 n}=O\left(3^{n}\right)$
e) $\sqrt{n} \log _{2}(n)=O(n)$
f) $\ln \left(n^{2}\right)=O(\ln (n))$

Answer 1

Aloha :)

Du musst hier prüfen, ob der Grenzwert (Limes Superior) der Quotienten exisitert.

zu a)$\quad\ln(n)+1=O(\sqrt n)\quad\checkmark$$$\lim\limits_{n\to\infty}\frac{\ln(n)+1}{\sqrt n}\stackrel{(\ln(n)<\sqrt n)}<\lim\limits_{n\to\infty}\frac{\sqrt n+1}{\sqrt n}=\lim\limits_{n\to\infty}\left(1+\frac{1}{\sqrt n}\right)=1$$

zu b)$\quad\binom{n}{2}=O(n^2)\quad\checkmark$$$\lim\limits_{n\to\infty}\frac{\binom{n}{2}}{n^2}=\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$$

zu c)$\quad2^{n+1}=O(2^n)\quad\checkmark$$$\lim\limits_{n\to\infty}\frac{2^{n+1}}{2^n}=2$$

zu d)$\quad3^{2n}=O(3^n)\quad\text{FAIL}$$$\lim\limits_{n\to\infty}\frac{3^{2n}}{3^n}=\lim\limits_{n\to\infty}\frac{3^n\cdot3^n}{3^n}=\lim\limits_{n\to\infty}3^n=\infty$$

zu e)$\quad\sqrt n\,\log_2(n)=O(n)\quad\checkmark$$$\lim\limits_{n\to\infty}\frac{\sqrt n\,\log_2(n)}{n}=\lim\limits_{n\to\infty}\frac{\sqrt n\,\frac{\ln(n)}{\ln(2)}}{n}\stackrel{(\ln(n)<\sqrt n)}<\lim\limits_{n\to\infty}\frac{\frac{n}{\ln(2)}}{n}=\frac{1}{\ln(2)}$$

zu f)$\quad n^2=O(\ln(n))\quad\text{FAIL}$$$\lim\limits_{n\to\infty}\frac{n^2}{\ln(n)}>\lim\limits_{n\to\infty}n=\infty$$

Comments

Vielen Dank für deine Antwort. Ich hatte noch  eine Frage: du teilst ja immer die Funktion durch O(f(x)), um zu schauen ob es dann für n gehen unendlich gegen 0 oder unendlich geht. Warum hast du bei a.) und e.) nochmal verglichen ob es dann kleiner ist als die Terme? Viele Grüße

---

Wir müssen ja zeigen, dass der Grenzwert existiert, daher habe ich die Original-Terme durch einfachere Terme abgeschätzt, sodass man die Konvergenz (a) btw. Divergenz (e) leichter erkennen kann.

---

Eine Frage noch. Stimmt das dann so:

a.) unbestimmt (<1 konvergent , >1 divergent)

b.) konvergent

c.) divergent

d.) divergent

e.) divergent

f.) divergent

---

a) $\ln (n)+1=O(\sqrt{n})$
b) $\left(\begin{array}{l}n \\ 2\end{array}\right)=O\left(n^{2}\right)$
c) $2^{n+1}=O\left(2^{n}\right)$
d) $3^{2 n}=O\left(3^{n}\right)$
e) $\sqrt{n} \log _{2}(n)=O(n)$
f) $\ln \left(n^{2}\right)=O(\ln (n))$

@Tschaka

Was hat dich bewogen, auf diesen Müll zu antworten?

Der Fragesteller hat sich sogar noch erdreistet, "Aufgabe" darüber zu schreiben.

Ich sehe keine Aufgabe. Ich vermisse eine Frage wie:

"Darf ich diese Zeilen blau unterstreichen?" oder

"Wie finde ich heraus, wie oft $"O"$ geschrieben wurde?" oder

"Was ist jeweils wahr bzw. falsch?" oder ... oder ... oder.

Dass du möglicherweise weißt, was der Fragesteller will ist noch lange kein Freibrief, so etwas ohne klärende Rückfrage in vorauseilendem Gehorsam zu beantworten.

---

Da hast du Recht Abakus. Tut mir leid. Ich war ein bisschen in Eile und ich habe tatsächlich übergelegt, wie ich die Frage stellen soll, aber das Thema ist schon länger her und ich wusste nicht mehr so richtig wie man das schreibt oder die Frage stellen soll. Du hast natürlich Recht, dass man sich die Zeit nehmen muss, die Frage richtig zu stellen. Tut mir leid