O Notation, Summenberechnung

11.05.2011, 10:04

Rose_xx

O Notation, Summenberechnung

Guten morgen!
Folgende Aufgabe soll ich berechnen:
$\begin{eqnarray*} \sum\limits_{i=0}^n x^{i} = O(n) \end{eqnarray*}$

das habe ich mir bis jetzt zusammenüberlegt, aber ich bin mir nicht 100% sicher, ob ich damit recht habe:

** edit(Abakus): bitte keine externen Links (die lassen sich ggf. nach kurzer Zeit schon nicht mehr nachvollziehen); du kannst sowas auch als Anhang hier hochladen bitte.

Thanks!
Rose

11.05.2011, 22:28

Abakus

Auf diesen Beitrag antworten »

RE: O Notation, Summenberechnung

Zitat:

Original von Rose_xx
Folgende Aufgabe soll ich berechnen:
$\begin{eqnarray*} \sum\limits_{i=0}^n x^{i} = O(n) \end{eqnarray*}$

Hallo,

wie lautet die Aufgabenstellung hier?

Grüße Abakus smile

11.05.2011, 23:19

Rose_xx

Auf diesen Beitrag antworten »

ach du meine güte, jetzt habe ich das wichtigste vergessen =D
und vielen dank für den tip mit dem anhang, das wusste ich noch gar nicht.
ich hatte es nur schon in word getippt und nochmal das ganze mit latex... da fand ich den screenshot praktischer =D

die aufgabenstellung war:
für welche $\begin{eqnarray*} x \in \mathbb R ^{+} \end{eqnarray*}$ gilt diese Gleichung

11.05.2011, 23:44

Abakus

Auf diesen Beitrag antworten »

Zitat:

Original von Rose_xx
die aufgabenstellung war:
für welche $\begin{eqnarray*} x \in \mathbb R ^{+} \end{eqnarray*}$ gilt diese Gleichung

OK. Für die Summe kennst du vermutlich auch die Formel für eine endliche geometrische Summe? Damit könntest du ggf. genauer arbeiten.

Was passiert, wenn x > 1 ist: dafür gilt es nicht dann? Dieser Beweis fehlt noch, denke ich.

Grüße Abakus smile

12.05.2011, 00:22

Rose_xx

Auf diesen Beitrag antworten »

die endliche geometrische Summe war.. Formelsammlung S. 51 - das weiß ich noch auswendig =D
$\begin{eqnarray*} s_{n} = a_{1} \cdot \frac {q^{n}-1} {q-1} \end{eqnarray*}$
und $\begin{eqnarray*} q \in \mathbb R ^{+} \end{eqnarray*}$ ohne 1

in meiner Summe ist q dann x. aber 1 darf man in der Formel ja definitiv nicht einsetzen - dann passt meine Aussage mit "1 ist dabei" irgendwie nicht =D

... bei x > 1 bin ich mir ziemlich unsicher. für mathematische beweise fehlt mir noch ein ansatz. aber logisch gedacht, darf ja $\begin{eqnarray*} x^{n} = O(n) \end{eqnarray*}$ nicht gelten ( Die Summanden $\begin{eqnarray*} x^{n-1} + x^{n-2} \end{eqnarray*}$ etc. dürfen laut Aussage meiner Tutorin ignoriert werden, da der größte Summand wichtig ist. Wiederum anders gedacht. Setzt man jetzt für x=1.1 und für n = 5 hat man ca. 1,61 = O(5) - sollte ja richtig sein.

meine güte, ich bin völlig verwirrt ):

ich habe natürlich auch schon nach sowas gegoogelt und bin auf folgende Formel gestoßen:
$\begin{eqnarray*} \sum\limits_{k=1}^n x^{k} = \frac {x^{n+1}-1}{x-1} - 1 \end{eqnarray*}$
mir selber ist diese Formel ungeläufig, so viel theoretische Mathematik hatte ich noch nicht. Deswegen kann ich nicht beurteilen, ob diese stimmt oder nicht.

12.05.2011, 21:59

Abakus

Auf diesen Beitrag antworten »

Zitat:

Original von Rose_xx
ich habe natürlich auch schon nach sowas gegoogelt und bin auf folgende Formel gestoßen:
$\begin{eqnarray*} \sum\limits_{k=1}^n x^{k} = \frac {x^{n+1}-1}{x-1} - 1 \end{eqnarray*}$
mir selber ist diese Formel ungeläufig, so viel theoretische Mathematik hatte ich noch nicht.

Das ist dieselbe Formel wie oben, nur mit dem Unterschied, dass der erste Summand nicht dabei ist (es geht ja erst bei k=1 los): von daher wird beim Ergebnis auch die 1 abgezogen, denn genau das wäre ja der erste Summand.

Zur Aufgabe: eine Möglichkeit ist, wenn du 3 Fälle unterscheidest:

1. $\begin{eqnarray*} x > 1 \end{eqnarray*}$

2. $\begin{eqnarray*} x = 1 \end{eqnarray*}$

3. $\begin{eqnarray*} x < 1 \end{eqnarray*}$

Grüße Abakus smile

12.05.2011, 23:06

Rose_xx

Auf diesen Beitrag antworten »

ah, okay, verstehe mit der Formel. ist ja total simple, die vielen Einser haben mich nur grad erschlagen.

ich verwende nun mal die endliche geometrische Summe.
Sollte x > 1 sein, geht der Bruch bei n -> unendlich gegen unendlich, da der Zähler immer größer wird

Bei x < 1 .. hmm.. würde ich wieder mit der geometrischen Reihe argumentieren. Denn setze ich bei der Formel Werte ein, schwanken die Ergebnisse schon sehr. Ich kann nur sagen, dass der Bruch (logischerweise) immer positiv bleibt und je größer das n wird, desto größer wird auch der Bruch (auch wenn es dann schon stark vom x abhängt, wie schnell)

Bei x = 1 ist klar, dass es nicht geht (wegen Nenner). Allerdings nur wenn man die Summenformel betrachtet. Ansonsten hätte ich ja gesagt man setzt bei $\begin{eqnarray*} f(n) <= c*g \end{eqnarray*}$ c = 2 und erhält damit, wenn man die 1 kürzt (soll ja gehen, die O-Notation ist mir immernoch leicht suspekt - wenn ich hier falsch liege, ich freue mich sehr über Verbesserungen hier. Aus meinem Skript.. und den Büchern werde ich einfach nicht schlau) n = O(n)

12.05.2011, 23:17

Abakus

Auf diesen Beitrag antworten »

Zitat:

Original von Rose_xx
ich verwende nun mal die endliche geometrische Summe.
Sollte x > 1 sein, geht der Bruch bei n -> unendlich gegen unendlich, da der Zähler immer größer wird

Ja, ok.

Zitat:

Bei x < 1 .. hmm.. würde ich wieder mit der geometrischen Reihe argumentieren. Denn setze ich bei der Formel Werte ein, schwanken die Ergebnisse schon sehr. Ich kann nur sagen, dass der Bruch (logischerweise) immer positiv bleibt und je größer das n wird, desto größer wird auch der Bruch (auch wenn es dann schon stark vom x abhängt, wie schnell)

Ja, wobei du hier eine Abschätzung verwendest: eine endliche Summe wird durch die unendliche Reihe abgeschätzt: das würde ich genau hinschreiben noch.

Zitat:

Bei x = 1 ist klar, dass es nicht geht (wegen Nenner). Allerdings nur wenn man die Summenformel betrachtet. Ansonsten hätte ich ja gesagt man setzt bei $\begin{eqnarray*} f(n) <= c*g \end{eqnarray*}$ c = 2 und erhält damit, wenn man die 1 kürzt (soll ja gehen, die O-Notation ist mir immernoch leicht suspekt - wenn ich hier falsch liege, ich freue mich sehr über Verbesserungen hier. Aus meinem Skript.. und den Büchern werde ich einfach nicht schlau) n = O(n)

Die Summenformel gilt für x=1 nicht, daher ist die hier nicht verwendbar. Du kennst jedoch die Summe durch einfaches Ausrechnen und weißt $\begin{eqnarray*} (n + 1) \in O(n) \end{eqnarray*}$ .

Grüße Abakus smile

12.05.2011, 23:29

Rose_xx

Auf diesen Beitrag antworten »

ha, ich seh endlich das ende der aufgabe (:

ich kann also sagen, dass es für $\begin{eqnarray*} 0<x\leq 1 \end{eqnarray*}$ gilt, weil:

1) x > 0, weil R+
2) 0<x<1 durch Abschätzung mit Hilfe der geometrischen Reihe [schreib ich natürlich so ausführlich wie möglich hin]
3) x = 1, weil (n+1) = O(n) [...]
4) x NICHT > 1, da:
$\begin{eqnarray*} \lim_{n \to \infty } a_{1} \cdot \frac {x^{n}-1}{x-1} = \infty \end{eqnarray*}$
müsste ich hier dann noch damit argumentieren, dass der Bruch "schneller" unendlich... bzw. "unendlicher" wird, als "n" alleine?

12.05.2011, 23:37

Abakus

Auf diesen Beitrag antworten »

Zitat:

Original von Rose_xx
4) x NICHT > 1, da:
$\begin{eqnarray*} \lim_{n \to \infty } a_{1} \cdot \frac {x^{n}-1}{x-1} = \infty \end{eqnarray*}$
müsste ich hier dann noch damit argumentieren, dass der Bruch "schneller" unendlich... bzw. "unendlicher" wird, als "n" alleine?

Hier ist $\begin{eqnarray*} a_1 = 1 \end{eqnarray*}$ erstmal, daher hier am besten weglassen. Ansonsten ja: wenn du den Ausdruck durch n teilst, bleibt er nicht beschränkt.

Grüße Abakus smile

12.05.2011, 23:48

Rose_xx

Auf diesen Beitrag antworten »

gut, dann tippe ich das morgen alles schön hin, das Bett ruft nach mir (:
Vielen lieben Dank für deine geduldige Hilfe!

Neue Frage »

Antworten »

O Notation, Summenberechnung

Verwandte Themen