Wahr oder falsch? (mit Begründung) a) für f(n)=10+n+3log n gilt f € O(n). b) Für f: N->[0,∞[gilt stets f € O(1+f²).

Question

Welche der folgenden Aussagen sind richtig, welche falsch?
kurze begründung!
a) für f(n)=10+n+3log n gilt f € O(n).
b) Für f: N->[0,∞[gilt stets f € O(1+f²).

 

unendlich ∞

O-Funktion

Answer 1

a) f(n)=10+n+3logn=O(1)+O(n)+O(logn)=O(n) => f € O(n)

b) Hier bin ich mir nicht sicher, wie man das mathematisch korrekt aufschreiben sollte. Anschaulich ist das ja klar, da f²+1>f für alle natürlichen Zahlen. Eventuell so:

Fall n=0: f(0)=0<1+0=1, also f € O(1+f²)

Fall n>=1: f(n)<f(n)²+1, also f € O(1+f²)