Et lite notat om kompleksitetsanalyse (O-notasjon)
Åsmund Eldhuset

(Hvis nettleseren din ikke bryter linjene, bare kopier teksten over i notepad, Word e.l.)

Meningen med O-notasjonen er å fremheve det leddet som har mest å si for hvor raskt en funksjon vokser. Betrakt f.eks. f(n) = 3n^2 - 73n + 1024. Selv om 1024 er et mye større tall enn 3, vil leddet 3n^2 bli mye større enn 1024 hvis bare n er stor nok. Tilsvarende vil ikke effekten av -73n heller være særlig merkbar hvis n er stor (f.eks. hvis n = 10000, da blir uttrykket 300000000 - 730000 + 1024). I tillegg kan det argumenteres for at den konstante koeffisienten 3 foran n^2 heller ikke har så mye å si. Det er to grunner til dette - for det første er det ofte slik at vi bruker O-notasjonen for å analysere funksjoner som beskriver tidsforbruket til dataprogrammer, og tidsforbruket vil variere (med en konstant faktor) ut ifra hvilket programmeringsspråk man bruker, hvor rask datamaskinen er, osv. Dessuten er det slik at uansett om det står n^2, 3n^2 eller 1000n^2, er det slik at hvis n blir dobbelt så stor, vil n^2 bli fire ganger så stor. Det er nettopp denne karakteristikken vi er ute etter å fremheve ved å si at funksjonen er O(n^2) - nemlig at en dobling av n vil føre til (omtrentlig) en firedobling av funksjonsverdien.

Men: O-notasjonen er en slags "mindre enn eller lik"-notasjon - formålet er å sette en øvre grense for hvor fort funksjonen vokser. Å si at f(n) = O(g(n)) betyr "f(n) vokser ihvertfall ikke raskere enn g(n) (innenfor en konstant faktor)". Derfor er det også *korrekt* å si at n^2 = O(n^3), og også at den er O(n^5), O(n^6) osv. (selv om det er mest *nøyaktig* å si at n^2 = O(n^2)). Omega-notasjonen tilsvarer "større enn eller lik", og Theta-notasjonen tilsvarer "lik".

Hurtigregelen for å svare på spørsmålet "er riktig at f(n) = O(g(n))?" er: finn det leddet i f med størst eksponent, og se bort fra konstanten foran. Kall eksponenten for a (altså var leddet n^a). Finn deretter det leddet i g med størst eksponent, fjern konstanten, og kall eksponenten for b. Da er f(n) = O(g(n)) hvis a <= b. Dessuten er f(n) = Omega(g(n)) hvis a >= b, og f(n) = Theta(g(n)) hvis a = b. Eksempelvis er 3n^2 - 73n + 1024 = O(2n^3 - n^2 + 42n + 8), fordi de største leddene er n^2 og n^3, og 2 <= 3.

Andre eksempler:
n^2 = O(n): nei
n^2 = O(n^2): ja
n^2 = O(n^3): ja
n^2 = Theta(n): nei
n^2 = Theta(n^2): ja
n^2 = Theta(n^3): nei
n^2 = Omega(n): ja
n^2 = Omega(n^2): ja
n^2 = Omega(n^3): nei