Seite Nr.:12
O(g) = {f: N ® R+ | $ n0
Das hat als Konsequenz, dass man eine “Gleichung” f = O(g) nur von links nach rechts
lesen kann. Eine Aussage O(g) = f ist sinnlos. Bei der Analyse von Algorithmen sind
gewöhnlich f, g: N ® N definiert, da das Argument die Größe der Eingabe und der Funktionswert
die Anzahl durchgeführter Elementaroperationen ist. Unter anderem wegen
Durchschnittsanalysen kann rechts auch R+ stehen.
Beispiel 1.7: Es gilt:
T1(n) = n + 3 = O(n) da n + 3 £ 2n "n ³ 3
T2(n) = 3n + 7 = O(n)
T3(n) = 1000n = O(n)
T4(n) = 695n2 + 397n + 6148 = O(n2)