Groß-O-Notation Gleichheit zeigen

Question

Die Aufgabe lautet wie folgt.

Zeigen Sie:

\O (log)=\O ({ log } ₁₀ )=\O (ln)=\O (log(2n))=\O (log(n+log(n))=\O (log({ n } ² ))

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))$$