Groß-O-Notation Gleichheit zeigen

Question

Die Aufgabe lautet wie folgt.

Zeigen Sie:

\O (log)=\O ({ log }_{ 10 })=\O (ln)=\O (log(2n))=\O (log(n+log(n))=\O (log({ n }^{ 2 }))

Mein Ansatz wäre nun zu zeigen, dass jede der Abschätzungen nach oben beschränkt ist und dabei Gleichheit herrscht. Heißt Grenzwert bilden und vielleicht noch mittels des Anstiegs an Stelle x eine gewisse Ähnlichkeit hervorheben.

Wäre für Feedback dankbar.

Comments

\( O (\log n)=O ({ \log }_{ 10 }n)=O (\ln n)=O (\log(2n))=O (\log(n+\log(n))=O (\log({ n }^{ 2 })) ?\)

Is das die Aufgabe? Was ist \( \log \)? Also welche Basis? 2?

---

Ja korrekt das ist die Aufgabe. Basis 2, richtig.

---

Du musst insgesamt 5 Mengengleichheiten zeigen. Wie habt ihr die Landau-Symbole definiert? Mir sind da schon mehrere verschiedene Definitionen begegnet, aber ich vermute mal, dass es in diesem Fall im Zusammenhang mit der Laufzeit von Algorithmen genutzt wird.

---

Lamdau-Symbol ist wie folgt definiert:

$$ O (f)=\{ g\in F|\exists { n }_{ 0 }\in N\quad \exists c\in N\quad \forall { n }\in N\quad mit\quad n>{ n }_{ 0 }\quad :\quad g(n)\le c*f(n)\} $$

Wobei N die natürlichen Zahlen mit 0 umfasst.

Korrekt, es geht dabei um die Laufzeit von Algorithmen.

---

Ok ich zeige mal exemplarisch die Gleichheit \( \mathcal{O}(\log n) = \mathcal{O}(\log_{10} n) \).

Als erstes zeige ich \( \mathcal{O}(\log n) \subseteq \mathcal{O}(\log_{10} n) \):

Sei \( f\in \mathcal{O}(\log n) \). Per Definition existieren dann \( c,n_0 >0 \), sodass für alle \(n>n_0\)

$$ f(n)\leqslant c\cdot \log n \tag{1}. $$

Mit den Logarithmengesetzen folgt \( \log n = \frac{\log_{10} n}{\log_{10} 2} \). Damit wird (1) zu

$$ f(n)\leqslant \underbrace{\frac{c}{\log_{10}2}}_{=:c'} \cdot \log_{10} n = c' \cdot \log_{10} n$$

für alle \(n>n_0\) und damit ist \(f\in \mathcal{O}(\log_{10} n)\) und da \(f\) beliebig war ist somit  \( \mathcal{O}(\log n) \subseteq \mathcal{O}(\log_{10} n) \) gezeigt.

Als nächstes zeige ich \( \mathcal{O}(\log n) \supseteq \mathcal{O}(\log_{10} n) \).

Sei dazu \( f\in \mathcal{O}(\log_{10} n)\). Per Definition gibt es \(c,n_0>0\), sodass für alle \(n>n_0\)

$$  f(n) \leqslant c\cdot \log_{10} n  \tag{2}. $$

Mit den Logarithmengesetzen erhält man wieder \( \log_{10} n = \frac{\log n}{\log 10} \) und damit analog zu oben für alle \(n>n_0\)

$$ f(n)\leqslant \underbrace{ \frac{c}{\log 10} }_{=:c'} \log n = c'\cdot \log n. $$

Also gilt \(f\in \mathcal{O}\log n) \) und da auch hier \(f\) beliebig war folgt daraus  \( \mathcal{O}(\log n) \supseteq \mathcal{O}(\log_{10} n) \).

Insgesamt also
\( \mathcal{O}(\log n) = \mathcal{O}(\log_{10} n) \).

Die anderen 5 Mengengleichheiten laufen so ähnlich ab. Es ist immer das selbe Prinzip, du musst das \( n_0\) und das \(c\), welches in der Definition auftaucht, konstruieren.

---

Das hilf mir doch schon weiter. Vielen Dank

---

Bisher klappt der Beweis sehr gut. Doch bei $$ \mathcal{O}(log(2n))=\mathcal{O}(log(n+log(n))$$ komme ich nicht weiter.

$$f\in \mathcal{O}(log(2n))\quad \Longrightarrow f\le c*log(2n)$$

Wenn ich nun $$log(2n) = log(2)+log(n)\neq log(n+log(n))$$

zu ersetzen versuche, stehe ich auf dem Schlauch.

Kann mir dort jemand einen Denkanstoss geben?

---

Habt ihr schon bewiesen, dass \( \log n = \mathcal{O}(n) \)? Das kann man da nutzen.

---

Bisher noch nicht. Wenn mir dass dabei hilft, werde ich es damit mal probieren. Danke

Answer 1

$$O (log n)=O ({ log }_{ 10 } n)=O (ln n)=O (log(2n))=O (log(n+log(n))=O (log({ n }^{ 2 }))$$


$$\log_2 n=\frac{\log_{10}n}{\log_{10}2}$$

Also:

$$\log_2 n \leq c \log_{10} n \text{ für } c=\frac{1}{\log_{10}2}$$

Also: $$O(\log n)=O(\log_{10} n)$$

$$\log(n) =O(n)$$
also $$\exists c>0, n_0 \in \mathbb{N} \text{ sodass } \forall n \geq n_0:$$

$$\log n \leq c n$$
Also:

$$\log( n+ \log n) \leq \log(n+cn)=\log(c(n+1))=\log c+ \log(n+1) \in O(\log(n+1)) \in O(\log(n^2))$$