matheraum.de
Raum für Mathematik
Offene Informations- und Nachhilfegemeinschaft

Für Schüler, Studenten, Lehrer, Mathematik-Interessierte.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Forenbaum
^ Forenbaum
Status Mathe
  Status Schulmathe
    Status Primarstufe
    Status Mathe Klassen 5-7
    Status Mathe Klassen 8-10
    Status Oberstufenmathe
    Status Mathe-Wettbewerbe
    Status Sonstiges
  Status Hochschulmathe
    Status Uni-Analysis
    Status Uni-Lin. Algebra
    Status Algebra+Zahlentheo.
    Status Diskrete Mathematik
    Status Fachdidaktik
    Status Finanz+Versicherung
    Status Logik+Mengenlehre
    Status Numerik
    Status Uni-Stochastik
    Status Topologie+Geometrie
    Status Uni-Sonstiges
  Status Mathe-Vorkurse
    Status Organisatorisches
    Status Schule
    Status Universität
  Status Mathe-Software
    Status Derive
    Status DynaGeo
    Status FunkyPlot
    Status GeoGebra
    Status LaTeX
    Status Maple
    Status MathCad
    Status Mathematica
    Status Matlab
    Status Maxima
    Status MuPad
    Status Taschenrechner

Gezeigt werden alle Foren bis zur Tiefe 2

Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Dt. Schulen im Ausland: Mathe-Seiten:Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
StartseiteMatheForenFolgen und ReihenLandau-Symbol (Big-O)
Foren für weitere Schulfächer findest Du auf www.vorhilfe.de z.B. Informatik • Physik • Technik • Biologie • Chemie
Forum "Folgen und Reihen" - Landau-Symbol (Big-O)
Landau-Symbol (Big-O) < Folgen und Reihen < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Folgen und Reihen"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Landau-Symbol (Big-O): Korrektur
Status: (Frage) beantwortet Status 
Datum: 10:59 Mo 18.02.2019
Autor: magics

Aufgabe
Beweisen oder widerlegen Sie die folgenden Aussagen:

a) [mm] $3^n \in 2^{O(n)}$ [/mm]
b) [mm] $(2^n)^3 \in 2^{O(n)}$ [/mm]
c) [mm] $2^{n^3} \in 2^{O(n)}$ [/mm]
d) [mm] $O(2^n) [/mm] = [mm] O(3^n)$ [/mm]
e) [mm] $O(n^2) [/mm] + O(n) = [mm] O(n^2)$ [/mm]
f) $O(n) - O(n) = O(0)$

Verwenden Sie die Tatsache, dass $f(n) [mm] \in O(g(n)),\; gdw.\; c,n_0 \in \IN,\; so\; dass\; \forall\; [/mm] n [mm] \ge n_0 \;gilt\; [/mm] f(n) [mm] \lt [/mm] c*g(n)$


Hallo,

ich habe die Aufgaben a) bis f) gelöst, wobei ich mir bei a), b), c) und f) nicht hundertprozentig sicher bin. Hier meine Lösungen:

a) [mm] $3^n \in 2^{O(n)}$ [/mm]
[mm] [quote]$3^n \in 2^{O(n)} \gdw log_2(3^n) [/mm] = O(n) [mm] \gdw n*log_2(3) \le [/mm] c*n [mm] \; [/mm] fuer [mm] \; [/mm] c >> 0$
[mm] \Rightarrow [/mm] Aussage wahr[/quote]

b) [mm] $(2^n)^3 \in 2^{O(n)}$ [/mm]
[mm] [quote]$(2^n)^3 \in 2^{O(n)} \gdw log_2(2^n)^3 [/mm] = O(n) [mm] \gdw n^3 \le [/mm] c*n [mm] \; [/mm] fuer [mm] \; [/mm] c >> 0$
[mm] \Rightarrow [/mm] Aussage wahr[/quote]

c) [mm] $2^{n^3} \in 2^{O(n)}$ [/mm]
[mm] [quote]$2^{n^3} \in 2^{O(n)} \gdw log_2(2^{n^3}) [/mm] = O(n) [mm] \gdw n^3 \le [/mm] c*n$
[mm] \Rightarrow [/mm] Aussage falsch, da [mm] $n^3 \ge [/mm] c*n [mm] \; [/mm] fuer [mm] \; [/mm] c>>0$[/quote]

d) [mm] $O(2^n) [/mm] = [mm] O(3^n)$ [/mm]
[mm] \Rightarrow [/mm] Aussage wahr, da [mm] $2^n \le 3^n$
[/mm]

e) [mm] $O(n^2) [/mm] + O(n) = [mm] O(n^2)$ [/mm]
[mm] [quote]$O(n^2) [/mm] + O(n) = [mm] O(max({n^2, n}) [/mm] = [mm] O(n^2)$ [/mm]
[mm] \Rightarrow [/mm] Aussage wahr[/quote]

f) $O(n) - O(n) = O(0)$
Sinngemäß steht da ja: "Etwas mit Linearer Komplexität minus etwas mit linearer Komplexität ist gleich Komplexität 0. Ich kenne aber nur Komplexität O(1) bei Konstanten, etwas wie O(0) macht gefühlsmäßig keinen Sinn, daher hätte ich gesagt: Aussage falsch."


Es wäre toll, wenn jemand meine Lösungen überfliegt und mich auf mögliche Irrtümer aufmerksam macht.

Beste Grüße
Thomas

        
Bezug
Landau-Symbol (Big-O): Antwort
Status: (Antwort) fertig Status 
Datum: 13:00 Mo 18.02.2019
Autor: HJKweseleit


> Beweisen oder widerlegen Sie die folgenden Aussagen:
>  
> a) [mm]3^n \in 2^{O(n)}[/mm]
>  b) [mm](2^n)^3 \in 2^{O(n)}[/mm]
>  c) [mm]2^{n^3} \in 2^{O(n)}[/mm]
>  
> d) [mm]O(2^n) = O(3^n)[/mm]
>  e) [mm]O(n^2) + O(n) = O(n^2)[/mm]
>  f) [mm]O(n) - O(n) = O(0)[/mm]
>  
> Verwenden Sie die Tatsache, dass [mm]f(n) \in O(g(n)),\; gdw.\; c,n_0 \in \IN,\; so\; dass\; \forall\; n \ge n_0 \;gilt\; f(n) \lt c*g(n)[/mm]
>  
> Hallo,
>  
> ich habe die Aufgaben a) bis f) gelöst, wobei ich mir bei
> a), b), c) und f) nicht hundertprozentig sicher bin. Hier
> meine Lösungen:
>  
> a) [mm]3^n \in 2^{O(n)}[/mm]
>  [mm]3^n \in 2^{O(n)} \gdw log_2(3^n) = O(n) \gdw n*log_2(3) \le c*n \; fuer \; c >> 0[/mm]
>  
> [mm]\Rightarrow[/mm] Aussage wahr [ok]
>  
> b) [mm](2^n)^3 \in 2^{O(n)}[/mm]
>  [mm](2^n)^3 \in 2^{O(n)} \gdw log_2(2^n)^3 = O(n) \gdw n^3 \le c*n \; fuer \; c >> 0[/mm]
>  
> [mm]\Rightarrow[/mm] Aussage wahr [ok]
>  
> c) [mm]2^{n^3} \in 2^{O(n)}[/mm]
>  [mm]2^{n^3} \in 2^{O(n)} \gdw log_2(2^{n^3}) = O(n) \gdw n^3 \le c*n[/mm]
>  
> [mm]\Rightarrow[/mm] Aussage falsch, da [mm]n^3 \ge c*n \; fuer \; c>>0[/mm]  [ok]
>  
> d) [mm]O(2^n) = O(3^n)[/mm]
>   [mm]\Rightarrow[/mm] Aussage wahr, da [mm]2^n \le 3^n[/mm]   ([ok])

Begründung würde mir nicht reichen, da aus [mm] O(2^n) [/mm] = [mm] O(3^n) [/mm] folgt: [mm] O(3^n) [/mm] = [mm] O(2^n), [/mm] und dann mjüsste auch [mm] 3^n<2^n [/mm] sein.
Nimm lieber wieder den Logarithmus.


>  
> e) [mm]O(n^2) + O(n) = O(n^2)[/mm]
>  [mm]O(n^2) + O(n) = O(max({n^2, n}) = O(n^2)[/mm]
>  
> [mm]\Rightarrow[/mm] Aussage wahr  [ok]
>  
> f) [mm]O(n) - O(n) = O(0)[/mm]
>  Sinngemäß steht da ja: "Etwas mit
> Linearer Komplexität minus etwas mit linearer Komplexität
> ist gleich Komplexität 0. Ich kenne aber nur Komplexität
> O(1) bei Konstanten, etwas wie O(0) macht gefühlsmäßig
> keinen Sinn, daher hätte ich gesagt: Aussage falsch."
>  

[ok]

Nimm z.B. [mm] O(x+\wurzel{x}) [/mm]  =O(x)



> Es wäre toll, wenn jemand meine Lösungen überfliegt und
> mich auf mögliche Irrtümer aufmerksam macht.
>  
> Beste Grüße
>  Thomas


Bezug
                
Bezug
Landau-Symbol (Big-O): Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 13:15 Mo 18.02.2019
Autor: magics

Besten Dank!

Bezug
        
Bezug
Landau-Symbol (Big-O): Antwort
Status: (Antwort) fertig Status 
Datum: 13:22 Mo 18.02.2019
Autor: Gonozal_IX

Hiho,

also da muss ich doch einiges Ergänzen, da deine Notation doch sehr gruselig ist:

> a) [mm]3^n \in 2^{O(n)}[/mm]
>  [mm]3^n \in 2^{O(n)} \gdw log_2(3^n) = O(n) \gdw n*log_2(3) \le c*n \; fuer \; c >> 0[/mm]
>  
> [mm]\Rightarrow[/mm] Aussage wahr

Dann kannst du doch bestimmt so ein $c$ angeben, für dass das gilt!
Und ein [mm] $n_0 \in \IN$ [/mm] noch dazu. Denn wähle ich mir $c=1 > 0$ und $n=1 [mm] \in \IN$ [/mm] so steht da [mm] $\log_2(3) \ge [/mm] 1$, was offensichtlich falsch ist.


> b) [mm](2^n)^3 \in 2^{O(n)}[/mm]
>  [mm](2^n)^3 \in 2^{O(n)} \gdw log_2(2^n)^3 = O(n) \gdw n^3 \le c*n \; fuer \; c >> 0[/mm]
>  
> [mm]\Rightarrow[/mm] Aussage wahr

Hier hast du am Ende stehen:  [mm] $n^3 \le [/mm] c*n$ und sagst: Aussage wahr.

aber hier:

> c) [mm]2^{n^3} \in 2^{O(n)}[/mm]
>  [mm]2^{n^3} \in 2^{O(n)} \gdw log_2(2^{n^3}) = O(n) \gdw n^3 \le c*n[/mm]

hast du das selbe stehen, und sagst:

> [mm]\Rightarrow[/mm] Aussage falsch, da [mm]n^3 \ge c*n \; fuer \; c>>0[/mm]

Ja was denn nun?

Und auch hier: Wenn wahr, dann c und [mm] n_0 [/mm] angeben, wenn falsch, zeigen, dass für beliebiges c und [mm] n_0 [/mm] ein n existiert, so dass [mm]n^3 > c*n[/mm]
Beachte das strikte größer Zeichen, denn bei Gleichheit wäre noch alles ok.
  

> d) [mm]O(2^n) = O(3^n)[/mm]
>   [mm]\Rightarrow[/mm] Aussage wahr, da [mm]2^n \le 3^n[/mm]

Wie vorher erwähnt: Reicht allein nicht, verwende noch a) dazu.

> e) [mm]O(n^2) + O(n) = O(n^2)[/mm]
>  [mm]O(n^2) + O(n) = O(max({n^2, n}) = O(n^2)[/mm]

Das erste Gleichheitszeichen ist zu begründen.  

> f) [mm]O(n) - O(n) = O(0)[/mm]
>  Sinngemäß steht da ja: "Etwas mit
> Linearer Komplexität minus etwas mit linearer Komplexität
> ist gleich Komplexität 0. Ich kenne aber nur Komplexität
> O(1) bei Konstanten, etwas wie O(0) macht gefühlsmäßig
> keinen Sinn, daher hätte ich gesagt: Aussage falsch."

Gegenfrage: Was ist $O(0)$? Die Menge kannst du direkt angeben.
Verwende doch mal die Definition! Was bedeutet $f [mm] \in [/mm] O(0)$?
Definition anwenden und Bedingung für f ablesen.

Gruß,
Gono

Bezug
                
Bezug
Landau-Symbol (Big-O): gelöscht
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 09:54 Di 19.02.2019
Autor: magics

Diese Mitteilung war ein Versehen. Siehe folgende Frage.
Bezug
                
Bezug
Landau-Symbol (Big-O): Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 09:57 Di 19.02.2019
Autor: magics

Hallo, meine Mitteilung sollte eigentlich eine Frage sein, deshalb poste ich sie hier erneut, als Frage:

> Hiho,
>  
> also da muss ich doch einiges Ergänzen, da deine Notation
> doch sehr gruselig ist:

Hallo Gono,

vielen Dank für deine vollkommen berechtigte Kritik! Ich sehe ein, was du sagst. Ich korrigiere nun meine Lösungen, wobei ich die Umformungsschritte weglasse. Bei f) bin ich trotzdem nicht so richtig weitergekommen.

a) [mm]3^n \in 2^{O(n)} \gdw n*log_23 = O(n)[/mm]
Somit gilt $n*log_23 [mm] \le [/mm] c * n $ für $c [mm] \ge [/mm] log_23$ und [mm] $n_0=0$ [/mm]

b) [mm](2^n)^3 \in 2^{O(n)} \gdw 3n = O(n)[/mm]
Somit gilt $3n [mm] \le [/mm] c*n$ für $c [mm] \ge [/mm] 3$ und [mm] $n_0 [/mm] = 0$

c) [mm]2^{n^3} \in 2^{O(n)} \gdw n^3 = O(n)[/mm]
[mm] $n^3$ [/mm] wächst aufgrund des polynomiellen Charakters insgesamt stärker als $c*n$, was sich bei bestimmten $c, [mm] n_0$ [/mm] nicht unbedingt sofort bemerkbar macht. Legt man fest [mm] $n_0=c=2 \in \IN$, [/mm] so gilt [mm] $2^3 [/mm] > [mm] 2^2$. [/mm] Damit ist die ursprüngliche Aussage widerlegt.

d) [mm]O(2^n) = O(3^n)[/mm]
Sei [mm] $2^n \in O(3^n)$, [/mm] so gilt [mm] $2^n \le c*3^n$ [/mm] für $c=1$ und [mm] $n_0=1$. [/mm]
Sei nun [mm] $\red{3^n \in O(2^n)}$, [/mm] so gilt [mm] $\red{3^n \le c*2^n}$ [/mm] für [mm] $\red{c \ge 2}$, [/mm] da [mm] $\red{\limes_{n\rightarrow\infty}\bruch{3^n}{2*(2^n)} = \limes_{}\bruch{3*3*...*3}{4*4*...*4} = 0}$ [/mm]
Wegen [mm] $\red{2^n \in O(3^n)$ und $\red{3^n \in O(2^n)}}$, [/mm] muss die Gleichheit gelten.

Das rote ist natürlich völliger Humbug.
[mm] $3^n \in O(2^n)$ [/mm] kann ja gar nicht korrekt sein. [mm] $\limes_{n\rightarrow\infty}\bruch{3^n}{c*(2^n)}$ [/mm] muss gegen Unendlich gehen, denn sei $c$ eine beliebige große Zahl, darstellbar als Zweierpotenz, also $c = [mm] 2^x$. [/mm] Dann wäre  [mm] $\limes_{n\rightarrow\infty}\bruch{3^n}{c*(2^n)} [/mm] = [mm] \limes_{n\rightarrow\infty}\bruch{3^n}{(2^{n+x})}=\bruch{\limes_{n\rightarrow\infty}3^n}{\limes_{n\rightarrow\infty}2^x*2^n)}$. [/mm] Und somit stünde wieder [mm] \limes_{n\rightarrow\infty}\bruch{3^n}{(2^n)} [/mm] zur Debatte, was nur gegen Unendlich gehen kann.
Also ist d) falsch.

e) [mm]O(n^2) + O(n) = O(n^2)[/mm]
Wegen [mm] $n^a \le O(n^b) \; \forall \; [/mm] a [mm] \le [/mm] b$ gilt $O(n) [mm] \subseteq O(n^2)$ [/mm] und somit [mm] $O(n^2) [/mm] + O(n) = [mm] O(max({n^2, n}) [/mm] = [mm] O(n^2)$ [/mm]

f) [mm]O(n) - O(n) = O(0)[/mm]
Nach Definition wäre $O(0)$ zu interpretieren als $f(n) [mm] \le [/mm] c*0$. Wenn ich mir das als Laufzeit eines Algorithmus vorstelle, ist das einfach gar nichts, also eher noch $f(n) = 0$, als $f(n) < 0$. Doch wie genau ich das interpretieren soll, verstehe ich nicht so ganz.

Grüße
Thomas


Bezug
                        
Bezug
Landau-Symbol (Big-O): Antwort
Status: (Antwort) fertig Status 
Datum: 20:34 Mi 20.02.2019
Autor: Gonozal_IX

Hiho,

> a) [mm]3^n \in 2^{O(n)} \gdw n*log_23 = O(n)[/mm]
>  Somit gilt
> [mm]n*log_23 \le c * n[/mm] für [mm]c \ge log_23[/mm] und [mm]n_0=0[/mm]

[ok]

> b) [mm](2^n)^3 \in 2^{O(n)} \gdw 3n = O(n)[/mm]
> Somit gilt [mm]3n \le c*n[/mm] für [mm]c \ge 3[/mm] und [mm]n_0 = 0[/mm]

[ok]

> c) [mm]2^{n^3} \in 2^{O(n)} \gdw n^3 = O(n)[/mm]
>  [mm]n^3[/mm] wächst
> aufgrund des polynomiellen Charakters insgesamt stärker
> als [mm]c*n[/mm],

Das ist korrekt (und man hätte hier fast aufhören können).

> was sich bei bestimmten [mm]c, n_0[/mm] nicht unbedingt sofort bemerkbar macht.

Das ist Palaver und keine Begründung.

> Legt man fest [mm]n_0=c=2 \in \IN[/mm], so
> gilt [mm]2^3 > 2^2[/mm]. Damit ist die ursprüngliche Aussage widerlegt.

Leider nicht. Du hast es nur für ein c widerlegt. Du musst aber zeigen, dass es kein einziges $c > 0$ gibt, so dass [mm] $n^3 \le [/mm] cn$ ab einem bestimmten [mm] $n_0$. [/mm]

Aber auch das ist kein Problem:
Sei [mm] $n_0 [/mm] > [mm] \sqrt{c}$ [/mm] dann gilt für alle $n [mm] \ge n_0$ [/mm] und beliebiges $c > 0$:
[mm] $n^3 [/mm] = [mm] n^2\cdot [/mm] n [mm] \ge n_0^2\cdot [/mm] n > [mm] \sqrt{c}^2\cdot [/mm] n = cn$, d.h.
[mm] $n^3 [/mm] > nc$

Damit ist das Gewünschte gezeigt.

> d) [mm]O(2^n) = O(3^n)[/mm]
>  Sei [mm]2^n \in O(3^n)[/mm], so gilt [mm]2^n \le c*3^n[/mm]
> für [mm]c=1[/mm] und [mm]n_0=1[/mm].
>  Sei nun [mm]\red{3^n \in O(2^n)}[/mm], so gilt [mm]\red{3^n \le c*2^n}[/mm]
> für [mm]\red{c \ge 2}[/mm], da
> [mm]\red{\limes_{n\rightarrow\infty}\bruch{3^n}{2*(2^n)} = \limes_{}\bruch{3*3*...*3}{4*4*...*4} = 0}[/mm]
>
> Wegen [mm]\red{2^n \in O(3^n)[/mm] und [mm]\red{3^n \in O(2^n)}}[/mm], muss
> die Gleichheit gelten.
>  Das rote ist natürlich völliger Humbug.
>  [mm]3^n \in O(2^n)[/mm] kann ja gar nicht korrekt sein.
> [mm]\limes_{n\rightarrow\infty}\bruch{3^n}{c*(2^n)}[/mm] muss gegen
> Unendlich gehen, denn sei [mm]c[/mm] eine beliebige große Zahl,
> darstellbar als Zweierpotenz, also [mm]c = 2^x[/mm]. Dann wäre  
> [mm]\limes_{n\rightarrow\infty}\bruch{3^n}{c*(2^n)} = \limes_{n\rightarrow\infty}\bruch{3^n}{(2^{n+x})}=\bruch{\limes_{n\rightarrow\infty}3^n}{\limes_{n\rightarrow\infty}2^x*2^n)}[/mm].
> Und somit stünde wieder
> [mm]\limes_{n\rightarrow\infty}\bruch{3^n}{(2^n)}[/mm] zur Debatte,
> was nur gegen Unendlich gehen kann.
>  Also ist d) falsch.

Kurz gesagt: Ja.
Deine Begründung kann man aber kürzen.
Damit die Aussage stimmt, müsste ja [mm] $3^n \in O(2^n)$ [/mm] gelten.
Wie du bereits erkannt hast, müsste dann aber gelten, dass
[mm] $\lim_{n\to\infty} \frac{3^n}{2^n} \le [/mm] c$

Es gilt aber [mm] $\lim_{n\to\infty} \frac{3^n}{2^n} [/mm] = [mm] $\lim_{n\to\infty} \left(\frac{3}{2}\right)^n [/mm] = [mm] +\infty$ [/mm]

Insbesondere gilt damit für alle $c > 0$, dass  [mm] $\lim_{n\to\infty} \frac{3^n}{2^n} [/mm] > c$

So hättest du übrigens auch die Aufgabe davor begründen können, nur dass man dort halt  stattdessen [mm] $\lim_{n\to\infty} n^2$ [/mm] betrachtet hätte.


> e) [mm]O(n^2) + O(n) = O(n^2)[/mm]
>  Wegen [mm]n^a \le O(n^b) \; \forall \; a \le b[/mm]
> gilt [mm]O(n) \subseteq O(n^2)[/mm] und somit [mm]O(n^2) + O(n) = O(max({n^2, n}) = O(n^2)[/mm]

Ok.

> f) [mm]O(n) - O(n) = O(0)[/mm]
>  Nach Definition wäre [mm]O(0)[/mm] zu
> interpretieren als [mm]f(n) \le c*0[/mm].

Erstmal: Ich nehme an, dass ihr nur nichtnegative Funktionen betrachtet?
Denn ganz allgemein bedeutet $f [mm] \in [/mm] O(g)$ nämlich $|f| [mm] \le [/mm] c|g|$

Dann: Du hast nun also $0 [mm] \le [/mm] f(n) [mm] \le c\cdot [/mm] 0 = 0$ für alle $n [mm] \ge n_0$ [/mm]
Was bedeutet das nun also für $f$?

Es bleibt f also nichts anderes übrig, als irgendwann Null zu werden.


> Wenn ich mir das als
> Laufzeit eines Algorithmus vorstelle, ist das einfach gar
> nichts, also eher noch [mm]f(n) = 0[/mm], als [mm]f(n) < 0[/mm]. Doch wie
> genau ich das interpretieren soll, verstehe ich nicht so
> ganz.

Wenn man noch annimmt, dass ein Algorithmus monoton wachsend in [mm] $n\in\IN$ [/mm] ist, bedeutet die Bedingung $f [mm] \in [/mm] O(0)$ also nichts anderes, dass $f$ die Nullfunktion sein muss!

D.h. im Allgemeinen gilt:
$f [mm] \in [/mm] O(0)$ bedeutet, dass $f$ irgendwann konstant Null wird ab einem [mm] $n_0 \in \IN$. [/mm]
Ist f zusätzlich monoton wachsend, wie bei einem Algorithmus, so ist $f$ von Anfang an konstant Null und damit die Nullfunktion.

Gebe also eine Funktion an, die in $O(n) - O(n)$ ist, aber nie Null wird und schon hast du  [mm]O(n) - O(n) \not= O(0)[/mm]  gezeigt.

Gruß,
Gono

Bezug
                                
Bezug
Landau-Symbol (Big-O): Merci
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 09:10 Do 21.02.2019
Autor: magics

Deine Hilfe war absolut der Hammer, vielen Dank!

Beste Grüße
Thomas

Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Folgen und Reihen"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.matheraum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]