aufwandsabschätzung

[Jeff_Mills]

F(n)+G(n)= O(max f(n),g(n))
F(n)-G(n)= Omega(minf(n),g(n))


welche aussagen sind falsch und welche wahr
danke

[eXe]

also das zweite is mal sicher falsch
f(n) = g(n)

0 != Omega(n)

das erste würd ich sagen is richtig aber beweisen könnt ichs net ;)

[SinusDiabolicus]

1 is richtig
2 is falsch

denk ich mal

[skytale]

glaub des erste ist auch falsch, z.B. f=-n², g=n

[SinusDiabolicus]

-n² geht doch nicht als aufwand¿
wenn mans für allgemeine funktionen betrachtet, ja, aber für aufwandseinschätzung? kann ich mir nicht vorstellen...

[Petzi]

ich würd auch mal sagen, dass das erste richtig und das zweite falsch ist
aber ganz sicher bin ich mir da auch net

[SinusDiabolicus]

naja, das erste stimmt, wenn man nichts negatives erlaubt (was ja zumindest laut definition für Theta, Omega und O auch so ist, da steht ja bei den bedingungen am anfang immer 0<=.....)

und das zweite stimmt zB nicht wenn f(n) und g(n) den gleichen grad haben, also zB
f=n²
g=n²+1
da wäre f(n)-g(n)=Omega(1)

zumindest soweit ich um die uhrzeit noch klar denken kann *lol* (ausserdem hat eXe schon ziemlich genauso argumentiert :-))