Landau-Notation

Neue Frage »

Tobus Auf diesen Beitrag antworten »
Landau-Notation
Hallo,
ich hab noch ein paar Fragen zur Landau-Notation:

Was klar ist, dass f $ \varepsilon $ O(g) bedeutet:f wächst nicht wesentlich schneller als g

Was bedeutet aber das hier:
-DTIME(O(f))=DTIME(f)

Bedeutet es, dass für eine Funktion, die nicht wesendlich langsamer als f wächst (O(f)) gilt, dass DTIME(nicht wesendlich langsamer wachsende Funktion)=DTIME(f) ?

DANKE
kiste Auf diesen Beitrag antworten »

.

Also gilt somit auf jeden Fall schon einmal . Die andere Richtung folgt aus dem Satz über Bandkompression.
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »