O Notation Grenzen Laufzeit

Question

Hallo ich bräuchte Hilfe bei der Landau Notation.  An sich ist mir das klar, dass diese Rechenregeln gelten, aber ich kann den Beweis nicht so runter schreiben. Vorallem wie man dann L'Hospital verwenden soll. Mir würde 1) und 2) schon reichen. 4) bekomm ich hin und hoffentlich auch die 3) wenn ich eins und zwei nachvollziehe

Comments

3. nochmals https://www.stacklounge.de/675/o-notation-beweis-laufzeit

Answer 1

Hi,

zur a):

Sei \(f \in O(n)\), d.h. \(|f(n)| \le  k \cdot  | n |\) für \(n\) groß genug und ein \(k>0\).

Wie kannst du \(k'\) wählen, sodass \(|f(n)| \le  k' \cdot  | c \cdot n |\)?

b)

Du musst zeigen, dass \(\lim_{n \to \infty} \frac{log_2(n)^2}{n} = 0\) gilt.

Es gilt: \((log_2(n)^2)'=\frac{2 \cdot log_2(n)}{n \cdot ln(2)}\) und \(n'=1\)

Du musst also zeigen, dass \(\lim_{n \to \infty} \frac{\frac{2 \cdot log_2(n)}{n \cdot ln(2)}}{1} =0\) gilt.

L'Hopital allgemein:

Grob: Gilt \(\lim_{x \to \infty} f(x)= \infty\) und \(\lim_{x \to \infty} g(x)= \infty\), so gilt:

\(\lim_{x \to \infty} \frac{f(x)}{g(x)}= \lim_{x \to \infty} \frac{f'(x)}{g'(x)}\)

Genauer: https://de.wikipedia.org/wiki/Regel_von_de_l%E2%80%99Hospital#Pr%C3%A4zise_Formulierung

Comments

a. ) k' < 0 vllt?

b.) da im zähler durch n dividiert wird und es gegen undendlich geht, wäre dann doch der bruch als ganzes gleich 0.

reicht das so? ich bin ersti und studiere informatik :/

---

also den zusammenhang zw der aufgabenstellung und deinem lösungsweg bei a) kann ich nicht wirklich nachvollziehen

---

Hi,

zur a):

\(k'<0\) ist nicht möglich. Die rechte Seite der Ungleichung wäre ja dann auf jeden Fall negativ und die linke ist immer größer gleich 0.

Du weißt, dass \(|f(n) | \le k \cdot |n|\) gilt.

Nun willst du \(k'\) so wählen, dass \(|f(n) | \le (k' \cdot | c |)  \cdot |n|\). Tipp: Dein \(k'\) darf von der Konstanten \(c\) abhängen.

b)

Das reicht leider nicht aus. Das gleiche Argument könntest du ja dann auch verwenden bei dem Bruch \(\frac{log_2(n)^2}{n^2}\). Hier geht der Nenner ja auch gegen unendlich.

Das Problem ist ja, dass sowohl Nenner als auch Zähler gegen unendlich gehen. Wenn das der Fall ist, kannst du l'Hopital (unter bestimmten Voraussetzungen, die z. B. auf Wikipedia stehen) nutzen.

Bei dem Bruch \(\frac{2 \cdot \log_2(n)}{n \cdot ln(2)}\) gehen sowohl Nenner als auch Zähler gegen unendlich. Hier musst du also wieder l'Hopital anwenden.

---

ok dann zur 1.) k=c ?

ne frage zur 3.) ich hab da jetzt auch l'hospital angewendet für den teil mit den beiden logarithmenfunktionen. habe als grenzwert  1/log2 und log2 raus. ist das jetzt falsch? oder kann man den da gar nicht anwenden?

---

die 2.) habe ich gelöst danke. aber die 3 leuchtet noch nicht ganz ein.

---

Wie hast du den dein \(k'\) gewählt?

Zur 3:

Erster Teil: L'Hopital funktioniert hier scheinbar nicht. Weiß aber gerade nicht warum, die Voraussetzungen sind erfüllt so wie ich das sehe. Arbeite mit \(\log_b(n)=\frac{\log_{10}(n)}{log_{10}(b)}\).

Zweiter Teil:

Du musst zeigen, dass \(2^n \le c \cdot 10^n\) für eine Konstante \(c\) gilt und für \(n\) beliebig groß. Das kannst du auch zeigen indem du zeigst, dass \(\lim_{n \to \infty}\frac{2^n}{10^n}=0 \) gilt.

Außerdem musst du begründen, warum \(\lim_{n \to \infty}\frac{10^n}{2^n} \neq 0 \)