Er det riktig å skrive $f(n)=O(n^2)$? Er ikke $O(n^2)$ en mengde? Burde det ikke være $f\in O(n^2)$?

Hensikten med notasjonen er å forenkle uttrykk, og å skjule unødvendige detaljer fra utregninger. Det gjør at det kan være nyttig med litt notasjonsmisbruk.

Asymmetri

Cormen mfl. gir et par regler for bruk av asymptotisk notasjon:1

  1. Asymptotisk notasjon i uttrykk og ligninger representerer bestemte, anonyme funksjoner.
  2. Når notasjonen forekommer til venstre i en ligning, må vi kunne velge den anonyme funksjonen fritt, og likevel få høyresiden til å bli rett.

Selv om $O(n)$ er definert som en mengde av funksjoner, så representerer altså notasjonen en bestemt (ukjent) funksjon når den brukes i uttrykk og ligninger, som f.eks. $f(n) = n^2 + O(n)$.

Regel nummer 2 er ikke lite rett frem, men kan enkelt oppsummeres slik:

Intuitivt kan vi si at de mulige tolkningene av venstresiden må utgjøre en delmengde av de mulige tolkningene av høyresiden.

Ta for eksempel følgende ligning:

\[n^2 + O(\lg n) = O(n^2)\]

I henhold til første regel, så betyr dette $n^2 + f(n) = g(n)$, der $f$ tilhører klassen $O(\lg n)$ og $g$ tilhører klassen $O(n^2)$. I henhold til den andre regelen, så må vi her kunne velge $f$ fritt, og likevel finne en $g$ så ligningen stemmer. I dette tilfellet er ikke det noe problem. Samme hvilken $f$ vi velger fra $O(\lg n)$, så kan vi definere $g(n)$ til å være $n^2 + f(n)$, og $g$ tilhører da $O(n^2)$. Det kan virke trivielt, men det er asymmetrisk:

\[O(n^2) \neq n^2 + O(\lg n)\]

Hvorfor? Fordi kravet er at samme hvilken funksjon $f$ vi velger fra $O(n^2)$ så skal vi kunne velge $g$ fra $O(\lg n)$ slik at $f(n)=n^2+g(n)$. Om vi f.eks. velger $f(n) = n^2 + n$ til venstre, får vi:

\[n^2 + n = n^2 + g(n)\]

Her finnes det ingen $g$ fra $O(\lg n)$ som får ligningen til å stemme.

Forenkling

Hva som menes med forenkling av et uttrykk med asymptotisk notasjon er ikke nødvendigvis helt utvetydig. En enkel definisjon kan f.eks. være:

Uttrykk $B$ er en forenkling av uttrykk $A$ dersom $A=B$ og $B$ er enklere enn $A$.

For eksempel kan vi forenkle $O(n^2 + n) + O(\lg n)$ til $O(n^2)$, siden

\[O(n^2 + n) + O(\lg n) = O(n^2)\]

og siden høyresiden er enklere. Med «enklere» mener vi f.eks. kortere (færre tegn) e.l. Dette er i seg selv litt upresist, men det er ikke der problemet ligger.

Slik definisjonen står, tillates også f.eks. følgende «forenkling»:

\[O(n^2 + n) + O(\lg n) = O(2^n)\]

Dette er en korrekt ligning, og høyresiden er enklere enn venstresiden, men det er ikke naturlig å kalle dette en forenkling, siden høyresiden opplagt er noe helt annet enn venstresiden. Dvs., uttrykket på høyresiden er mye mindre presist enn venstresiden.

Heller enn å si at dette ikke kan regnes som en forenkling, så sier vi at det er en upresis forenkling, og innfører følgende retningslinje:

Forenkling bør medføre minst mulig tap av presisjon.

Av og til kan noe tap av presisjon være nyttig, men om du ikke har noen spesiell grunn til å bruke en upresis forenkling, bør du bruke en presis forenkling (der høyre og venstre side kan byttes om).

Merk at dette gjelder spesifikt for forenkling. Det kan jo f.eks. hende du blir bedt om å skrive et uttrykk med asymptotisk notasjon, og da må du naturligvis gi slipp på presisjon – det er jo hele poenget. Men ikke gi slipp på mer presisjon enn du må! F.eks. kan du skrive $3n+2$ som $\Theta(n)$, men ikke skriv f.eks. $O(n^2)$, med mindre du har grunn til det!

Men om du blir spurt om $O(n^2)$ er en forenkling av $3n+2$, så er svaret like fullt «ja»; det er bare en upresis forenkling.

  1. Asymptotic notation in equations and inequalities, s. 49. ↩