Groß O-Notation im Exponenten.

21.10.2017, 14:53	Max_K.	Auf diesen Beitrag antworten »
Groß O-Notation im Exponenten. Meine Frage: Hallo Matheboard. ich habe eine Frage, und zwar muss ich zeigen (oder widerlegen), dass: $\begin{eqnarray} 3^{O(n)} = O(8^{n}) \end{eqnarray}$ Meine Ideen: Meine Überlegung war, dass hier als f(n) ja eine lineare Funktion im Exponenten steht, und 3 zur Basis. Mein g(n) ist eine Exponentialfunktion, mit 8 zur Basis. Also müsste das ja eigentlich stimmen. Schwierigkeiten macht mir das O(n) im Exponenten. Bin mir nicht sicher ob mit Limes oder ob ein geeignetes c zu finden der schönere Weg ist. Bin jedenfalls ratlos wie ich hier am besten beginne.
21.10.2017, 14:55	IfindU	Auf diesen Beitrag antworten »
RE: Groß O-Notation im Exponenten. Was steht denn auf der linken Seite, wenn dort das $\begin{eqnarray} O(n) \end{eqnarray}$ durch die lineare Funktion $\begin{eqnarray} n \mapsto 2n \end{eqnarray}$ ersetzt wird.
21.10.2017, 14:58	Max_K.	Auf diesen Beitrag antworten »
Hi! Wenn ich deine Frage richtig verstehe dann: $\begin{eqnarray} 3^{2n} \end{eqnarray}$
21.10.2017, 14:59	IfindU	Auf diesen Beitrag antworten »
Genau. Und das ist nach Potenzgesetzen also $\begin{eqnarray} 3^{2n} = (3^2)^n = \ldots \end{eqnarray}$ . Ist das wirklich asymptotisch durch $\begin{eqnarray} 8^n \end{eqnarray}$ beschränkt?
21.10.2017, 15:05	Max_K.	Auf diesen Beitrag antworten »
Also wenn ich das so lese dann nein. Da es für $\begin{eqnarray} 9^{n} <= c8^{n} \end{eqnarray}$ niemals ein c geben wird, welches ab einem gewissen n0 alle $\begin{eqnarray} 8^{n} \end{eqnarray}$ bzw mein $\begin{eqnarray} g(n) \end{eqnarray}$ größer werden bzw. bleiben lässt als mein $\begin{eqnarray} f(n) \end{eqnarray}$ . Kann/darf man das so argumentieren? Eine beliebige Funktion aus $\begin{eqnarray} O(n) \end{eqnarray*}$ nehmen, um zu zeigen, dass es nicht möglich ist? (Sofern das die richtige Idee ist)
21.10.2017, 15:11	IfindU	Auf diesen Beitrag antworten »
Genau das meinte. Und wenigstens so wie ich die Frage verstehe. Ich lese das so $\begin{eqnarray} 3^{O(n) } = \{ f: \mathbb N \to \mathbb R \mid \text{ es gibt eine Funktion } g \in O(n), \text{ so dass } f(n) = 3^{g(n)} \} \end{eqnarray}$ . Und die Frage ist, ob $\begin{eqnarray} f \in 3^{O(n)} \implies f \in O(8^n) \end{eqnarray}$ . Und du hast dir $\begin{eqnarray} f = 3^{2n} \end{eqnarray}$ definiert und gezeigt, dass die Implikation nicht stimmt. Eine schöne Begründung ist übrigens, dass $\begin{eqnarray} 9^n \leq c 8^n \end{eqnarray}$ nicht stimmen kann, ist durch $\begin{eqnarray} 8^n \end{eqnarray}$ zu teilen, d.h. $\begin{eqnarray} \left ( \frac 9 8 \right)^n \leq c \end{eqnarray}$ zu haben. Die linke Seite divergiert gegen unendlich, kann also nicht durch eine Konstante beschränkt sein.
Anzeige

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »