1.1 Asymptotisk notasjon — de fem symbolene

De fem asymptotiske symbolene `O, Ω, Θ, o, ω` med formelle definisjoner — grunnlaget alle kjøretidssvar hviler på.

45 min

8 oppgaver

Asymptotisk notasjonde fem symbolene

Din fremgang i kapitlet

0 / 8 oppgaver

Kapitlets plass i kurset

Brukes videre i

1.2Forenkling av asymptotiske uttrykk 1.4Rekurrenser — masterteoremet 3.4Hashing

De fem symbolene $O$ , $\Omega$ , $\Theta$ , $o$ og $\omega$ er tema i
100 % (17 av de 17 settene i grunnlaget). Ingen annen enkeltbit av pensum er
like forutsigbar, og ingen annen er like billig å sikre seg.

Symbolene kommer i tre sjangre, og alle tre skrives ut i klarspråk her:

- Sjanger D — definisjon, altså at du blir bedt om å skrive ned den presise
definisjonen av ett av symbolene. Dette er et fast, direkte krav.
- Sjanger A — asymptotisk forenkling, altså at du skal koke et sammensatt
uttrykk ned til ett strammeste svar. Den trenes for fullt i neste kapittel,
men hviler helt på definisjonene du lærer her.
- Sjanger E — kjøretid, altså at du skal oppgi kjøretiden til en algoritme i
ett uttrykk. Her avgjør det om du velger $O$ eller $\Theta$ .

Alle tre er kortsvarsoppgaver: du får noen få linjer til rådighet, og det er
svaret som teller, ikke veien dit. Eksamen har dessuten hjelpemiddelkode E,
som er kodeordet for at ingen hjelpemidler er tillatt — verken bok, formelark
eller kalkulator. Definisjonene under må derfor kunnes utenat, ordrett nok til at
du kan skrive dem ned uten å tenke deg om.

Prioritet: høyeste prioritet — dette må sitte.

Slik er kapitlet lagt opp (45 min): først et konkret anker for hva
«asymptotisk» egentlig betyr, så de fem definisjonene én etter én med en oppgave
rett etter hver bit, deretter vekstordningen du bruker til å sammenligne
funksjoner i hodet, og til slutt de tre reglene som lar deg kombinere påstander.
Begrepsbanken helt nederst er repetisjonsstoff.

Forkunnskaper

Dette er bokas første faglige kapittel, og det forutsetter ingen andre kapitler.
Alt som brukes, forklares her.

To oppslag fra videregående gjør lesningen lettere. Begge er valgfrie:

- Potenser og logaritmer — hva en logaritme er, og hvorfor
grunntallet bare er en konstant faktor. Vi bruker $\lg n$ hele veien.
- Mengdelære — $O(g(n))$ er egentlig navnet på en mengde av
funksjoner, og ordet «tilhører» er nøyaktig det du trenger for å lese
notasjonen riktig.

Har du aldri sett en kjøretid skrevet som $O(\text{noe})$ før, er
Algoritmedefinisjon, pseudokode og kompleksitet (Big-O)
et mykere første møte. Den boka nøyer seg med $O$ ; her skal du lære alle fem.

Notasjons- og pseudokodeliste

Hvorfor vi teller vekst og ikke sekunder

Se for deg at en nettbutikk skal finne den dyreste varen i katalogen sin. Med
1 000 varer merker ingen at programmet i det hele tatt kjørte. Med 10 millioner
varer merker alle det. Spørsmålet som betyr noe er ikke «hvor mange sekunder tok
det på min maskin?», men «hva skjer når katalogen blir ti ganger så stor?».

Det er nettopp det spørsmålet asymptotisk analyse svarer på. Vi teller ikke
sekunder — sekunder avhenger av maskinen, av programmeringsspråket og av hvor
mye annet som kjørte samtidig. Vi teller hvordan arbeidsmengden vokser med
størrelsen på inndataene, og vi kaller den størrelsen $n$ .

Arbeidet skriver vi som en funksjon $T(n)$ . Å gå gjennom et array med $n$
elementer én gang gir $T(n) = n$ sammenligninger, kanskje $T(n) = 3n + 20$ hvis
du teller med oppstart og bokføring. Poenget med asymptotisk notasjon er at de
to uttrykkene skal behandles likt: begge dobler seg når $n$ dobles, og det er
den egenskapen som overlever bytte av maskin.

Asymptotisk vekst

n

📜Pseudokode-kontrakt: `Maximum`

Antagelser om representasjon. Arrayet er A[1..n] med indeks fra 1, slik
CLRS skriver det. Elementene kan sammenlignes to og to.

Prebetingelse: A har minst ett element. Postbetingelse: returverdien er
det største elementet i A[1..n], og A er uendret.

Maximum(A)
  Input:  array A[1..n], n >= 1
  Output: det storste elementet i A[1..n]
  storst = A[1]
  for i = 2 to A.length
      if A[i] > storst
          storst = A[i]
  return storst
  Kjoretid: Theta(n)

Grunnideen i én setning: etter at løkka har behandlet indeks $i$ , er storst
lik det største elementet i A[1..i], så når løkka er ferdig gjelder det for
hele arrayet.

Kjøretid: løkka kjører nøyaktig $n-1$ runder uansett hvordan tallene ligger,
og hver runde koster en fast mengde arbeid, altså $T(n) = \Theta(n)$ .

Dette er den enkleste kjøretiden som finnes, og den er et godt anker: alt annet i
kapitlet handler om hvordan man sier presist at én slik funksjon vokser fortere
eller saktere enn en annen.

Det første symbolet: et tak

Anta at du har talt opp arbeidet i et program og fått $T(n) = 3n + 20$ . Du vil si
noe kort og sant om det. Den svakeste, men mest brukte påstanden er: det vokser
høyst like fort som $n$ .

Presist betyr det at du kan finne en konstant å gange $n$ med, slik at $3n + 20$
holder seg under den fra et punkt av. Med $c = 5$ er $5n$ større enn $3n + 20$
så snart $n \ge 10$ : $3 \cdot 10 + 20 = 50$ og $5 \cdot 10 = 50$ , og for større
$n$ vokser $5n$ fortest. Det er hele innholdet i $O$ .

O(g(n))

— øvre grense

O(g(n))

Vitnene

c

n_0

(c, n_0)

📝Oppgave 1

(Innstegsoppgave, sjanger D — definisjon, altså at du skriver ned den presise
definisjonen av et symbol.)

a) Skriv definisjonen av $f(n) = O(g(n))$ med egne ord, og få med både $c$
og $n_0$ .
b) Vis at $7n + 100 = O(n)$ ved å oppgi ett gyldig vitne $(c, n_0)$ .

De to neste: et gulv, og begge deler samtidig

$O$ alene er ofte for lite. Sier du at en algoritme bruker $O(n^2)$ tid, har du
ikke utelukket at den egentlig er ferdig på $\Theta(n)$ — du har bare lovet at
den ikke er verre enn kvadratisk. For å si at noe faktisk koster så mye,
trenger du et gulv i tillegg til taket.

Gulvet heter $\Omega$ , og det er den samme definisjonen med ulikheten snudd. Har
du både tak og gulv med samme $g$ , sier du at $f$ vokser nøyaktig som $g$ — og
det symbolet heter $\Theta$ .

\Omega(g(n))

— nedre grense

\Omega(g(n))

\Theta(g(n))

— tett grense

\Theta(g(n))

✏️Eksempel 1: $3n^2 + 5n = \Theta(n^2)$ med eksplisitte vitner

Vis at $3n^2 + 5n = \Theta(n^2)$ ved å oppgi konkrete konstanter $c_1$ , $c_2$ og
$n_0$ .

Vi må klemme

3n^2 + 5n

mellom to konstantganger av

n^2

Nedre grense. Leddet $5n$ er positivt for alle $n \ge 1$ , så

$3n^2 + 5n \ge 3n^2 \quad \text{for alle } n \ge 1.$

Det gir $c_1 = 3$ og $n_0 = 1$ .

Øvre grense. Vi vil ha $3n^2 + 5n \le c_2 n^2$ . Prøv $c_2 = 4$ : ulikheten
blir $5n \le n^2$ , altså $5 \le n$ . Så

$3n^2 + 5n \le 4n^2 \quad \text{for alle } n \ge 5.$

Sett sammen. Med $c_1 = 3$ , $c_2 = 4$ og $n_0 = 5$ gjelder begge ulikhetene
samtidig:

$3n^2 \le 3n^2 + 5n \le 4n^2 \quad \text{for alle } n \ge 5.$

Altså er $3n^2 + 5n = \Theta(n^2)$ .

Kortsvarsformen: på eksamen skriver du én linje — $\Theta(n^2)$ , med
$c_1 = 3$ , $c_2 = 4$ , $n_0 = 5$ — og ikke hele utledningen. Utregningen over er
undervisning, ikke svar.

Intuisjon: legg merke til at $n_0 = 5$ ikke er noe magisk tall. Hadde vi
valgt $c_2 = 8$ , ville $5n \le 5n^2$ holdt allerede fra $n = 1$ . Konstantene og
grensen henger sammen, og du får velge dem som passer deg.

📝Oppgave 2

Sjanger A

Avgjør for hver av påstandene om den er sann eller gal, og begrunn hver med én
setning.

a) $6n^2 + 3n + 9 = \Theta(n^2)$
b) $6n^2 + 3n + 9 = O(n^3)$
c) $6n^2 + 3n + 9 = \Theta(n^3)$

De to strenge: $o$ og $\omega$

De tre symbolene så langt sammenligner opp til en konstant. $3n^2$ og $5n^2$ er
$\Theta$ av hverandre — konstanten 3 mot 5 spiller ingen rolle. Noen ganger vil
du si noe sterkere: at $f$ virkelig blir liten i forhold til $g$ , uansett hvor
mye du får lov til å gange $g$ ned med.

Det er nettopp der $o$ og $\omega$ kommer inn, og forskjellen fra $O$ og $\Omega$
ligger i ett eneste ord. Der $O$ sier «det finnes en $c$ », sier $o$ «for hver
$c$ ». Klarer du å holde de to fra hverandre, har du sikret deg mot den vanligste
feilen i sjanger D.

o(g(n))

— strengt mindre

o(g(n))

\omega(g(n))

— strengt større

\omega(g(n))

«For hver

c

» kontra «det finnes en

c

O

Typiske feil

Å blande $O$ og $\Theta$ . Har du vist et tak, har du vist

O

\Theta

krever gulv i tillegg. Skriver du

\Theta(n^2)

etter bare å ha vist

3n^2 + 5n \le 4n^2

, har du påstått mer enn du har belegg for.

Å gi en løsere grense enn nødvendig — felle #4, altså å oppgi en løs
asymptotisk grense der en strammere finnes. $6n^2 + 3n + 9 = O(n^3)$ er sant,
men et svar som kaster bort informasjon. Kan du vise $\Theta(n^2)$ , er det
$\Theta(n^2)$ som er svaret. Regelen er kort: oppgi alltid det strammeste
uttrykket du kan forsvare.

Å glemme «for hver $c$ » i $o$ og $\omega$ . En definisjon av $o$ som bare
sier «det finnes en $c$ » beskriver $O$ , ikke $o$ , og gir ikke uttelling som
definisjon av $o$ .

Å definere $\Omega$ uten $n_0$ . « $f$ er minst like stor som $g$ » er ikke
definisjonen. Ulikheten kreves bare for $n \ge n_0$ , og bare opp til konstanten
$c$ . Uten $n_0$ ville $n^2 = \Omega(n)$ vært galt, siden $n^2 < n$ er usant bare
for $n = 0$ og $n = 1$ — grensen finnes nettopp for å slippe å tenke på slike
tilfeller.

Å bytte om venstre- og høyreside. Du skriver $f(n) = O(g(n))$ , aldri
$O(g(n)) = f(n)$ . Notasjonen leses fra venstre mot høyre og kan ikke snus.

✏️Eksempel 2: alle fem symbolene på samme funksjon

La $f(n) = 3n^2 + 5n$ . Avgjør for hver av $g(n) = n$ , $g(n) = n^2$ og
$g(n) = n^3$ hvilke av de fem symbolene som gjelder.

Metoden er alltid den samme: se på forholdet

f(n)/g(n)

når

n

vokser. Går det
mot null, er

f = o(g)

. Går det mot uendelig, er

f = \omega(g)

. Holder det seg
mellom to positive konstanter, er

f = \Theta(g)

Mot $g(n) = n^2$ . Forholdet er $3 + 5/n$ , som nærmer seg 3. Det er verken
null eller uendelig, så

$3n^2 + 5n = \Theta(n^2), \quad \text{og dermed også } O(n^2) \text{ og } \Omega(n^2).$

Verken $o(n^2)$ eller $\omega(n^2)$ gjelder — de utelukkes av $\Theta$ .

Mot $g(n) = n^3$ . Forholdet er $3/n + 5/n^2$ , som går mot null. Da er

$3n^2 + 5n = o(n^3), \quad \text{og dermed også } O(n^3).$

$\Omega(n^3)$ , $\Theta(n^3)$ og $\omega(n^3)$ er alle gale.

Mot $g(n) = n$ . Forholdet er $3n + 5$ , som vokser uten grense. Da er

$3n^2 + 5n = \omega(n), \quad \text{og dermed også } \Omega(n).$

$O(n)$ , $\Theta(n)$ og $o(n)$ er alle gale.

Legg merke til mønsteret. $o$ trekker alltid $O$ med seg, og $\omega$ trekker
alltid $\Omega$ med seg — men aldri motsatt vei. Det strammeste svaret er alltid
$\Theta$ der $\Theta$ finnes, og her finnes den bare mot $n^2$ .

📝Oppgave 3

Sjanger D og A blandet

Bruk forholdet $f(n)/g(n)$ til å avgjøre påstandene.

a) Er $100n = o(n^2)$ ?
b) Er $n\lg n = o(n^2)$ ?
c) Er $n\lg n = O(n^2)$ ?
d) Er $n\lg n = o(n\lg n)$ ?

Symbolene som ulikhetstegn

Når definisjonene sitter, er det verdt å ha en kortversjon i hodet også. De fem
symbolene oppfører seg som fem ulikhetstegn mellom vekstratene til $f$ og $g$ :

Symbol	Leses som	Ulikhetstegnet det minner om
$f = O(g)$	« $f$ vokser høyst like fort som $g$ »	mindre enn eller lik
$f = \Omega(g)$	« $f$ vokser minst like fort som $g$ »	større enn eller lik
$f = \Theta(g)$	« $f$ vokser nøyaktig like fort som $g$ »	lik
$f = o(g)$	« $f$ vokser strengt saktere enn $g$ »	strengt mindre enn
$f = \omega(g)$	« $f$ vokser strengt fortere enn $g$ »	strengt større enn

Tabellen er en huskeregel, ikke en definisjon, og den har én viktig svakhet: for
tall gjelder at enten er

a \le b

eller

b \le a

. For funksjoner finnes det par
der ingen av delene gjelder —

n

n^{1 + \sin n}

krysser hverandre i det
uendelige. Slike par dukker ikke opp i dette faget, men skriv aldri tabellen som
om den var definisjonen. På et definisjonsspørsmål er det $\exists c, n_0$ -formen
som gir uttelling.

Rangeringen du bruker i hodet

Nesten alle klassifiseringsspørsmål på eksamen løses ved å plassere de to
funksjonene i denne rekkefølgen:

$1 < \lg n < n < n\lg n < n^2 < n^3 < 2^n < n!$

Ligger $f$ til venstre for $g$ , er $f = o(g)$ . Ligger de på samme plass, er
$f = \Theta(g)$ . Ligger $f$ til høyre, er $f = \omega(g)$ .

Tallene gjør poenget tydelig. For $n = 1024$ :

Funksjon	Verdi ved $n = 1024$
$1$	1
$\lg n$	10
$n$	1 024
$n\lg n$	10 240
$n^2$	1 048 576
$n^3$	1 073 741 824
$2^n$	astronomisk
$n!$	enda større

Tre ting er verdt å merke seg. Konstanter forsvinner:

n/2

5n

100n + 7

er alle

\Theta(n)

. Grunntallet i en logaritme forsvinner også:

\log_{10} n = \lg n / \lg 10

, og

\lg 10

er bare en konstant, så

\log_{10} n = \Theta(\lg n)

. Og en logaritme inne i en potens blir en
konstantfaktor:

\lg(n^3) = 3\lg n = \Theta(\lg n)

📝Oppgave 4

Sjanger A

Sorter disse sju funksjonene fra langsomst til raskest voksende, og
oppgi for hvert nabopar hvilket symbol som knytter dem sammen.

$n^3, \quad \lg n, \quad n!, \quad n\lg n, \quad n^2\lg n, \quad 2^n, \quad n$

Regler du får bruke uten å bevise dem

Symbolene oppfører seg som ulikhetstegn også når du setter påstander sammen. De
tre reglene under brukes fritt i fasitene, og du trenger ikke bevise dem — men du
må vite at de finnes, og hvilken vei de går.

📜Transitivitet, symmetri og

\Theta

som ekvivalensrelasjon

Transitivitet. Alle fem symbolene er transitive. Er

f = O(g)

g = O(h)

, så er

f = O(h)

. Det samme gjelder for

\Omega

\Theta

o

\omega

hver for seg. Dette er grunnen til at vekstordningen fungerer som en
kjede: har du plassert to funksjoner i den, vet du hvordan de forholder seg til
alle de andre.

Symmetriregelen mellom $O$ og $\Omega$ . Det gjelder at

$f(n) = O(g(n)) \iff g(n) = \Omega(f(n)).$

Samme sak sett fra hver sin side. Tilsvarende er $f = o(g)$ det samme som
$g = \omega(f)$ .

$\Theta$ er en ekvivalensrelasjon. Den er refleksiv ( $f = \Theta(f)$ ),
symmetrisk (er $f = \Theta(g)$ , så er $g = \Theta(f)$ ) og transitiv. Praktisk
betyr det at «vokser like fort som» deler funksjonene inn i klasser: $n/2$ , $5n$
og $100n + 7$ havner i samme klasse, og du kan bytte fritt mellom dem inne i et
asymptotisk uttrykk. Vi bruker egenskapen; vi beviser den ikke.

Merk at $O$ og $\Omega$ ikke er symmetriske: $n = O(n^2)$ er sant, mens
$n^2 = O(n)$ er galt.

Likhetstegnet i asymptotisk notasjon

O(g(n))

\lg n

— toerlogaritmen

\lg n

📝Oppgave 5

Sjanger F

Avgjør om hver påstand stemmer.

a) Hvis $f = O(g)$ og $g = O(h)$ , så er $f = O(h)$ .
b) Hvis $f = O(g)$ , så er $g = O(f)$ .
c) Hvis $f = \Theta(g)$ , så er $g = \Theta(f)$ .
d) Hvis $f = O(g)$ , så er $g = \Omega(f)$ .

✏️Eksempel 3: eksamensnivå — definisjon og klassifisering i ett

a) Definér

\omega(g(n))

presist, og forklar med én setning hva som skiller
det fra

\Omega(g(n))

b) Avgjør om $n\lg n = \omega(n)$ og om $n\lg n = \omega(n\lg n)$ .

c) En algoritme har kjøretid $T(n)$ , og du har vist at $T(n) \le 4n^2$ for
alle $n \ge 8$ . Hvilket av de fem symbolene har du belegg for?

f(n) = \omega(g(n))

betyr at det for hver konstant

c > 0

finnes en
grense

n_0 > 0

slik at

0 \le c\,g(n) < f(n)

for alle

n \ge n_0

Forskjellen fra $\Omega$ : $\Omega$ krever bare at ulikheten holder for én
konstant $c$ , mens $\omega$ krever at den holder for hver eneste $c$ , uansett hvor
stor.

b) $n\lg n = \omega(n)$ er sant: forholdet er $\lg n$ , som vokser uten grense,
så uansett hvor stor $c$ er finnes det en $n_0$ der $\lg n$ passerer den.

$n\lg n = \omega(n\lg n)$ er galt. Ingen funksjon er $\omega$ av seg selv —
allerede $c = 1$ gir ulikheten $n\lg n < n\lg n$ , som aldri holder.

c) Du har belegg for $T(n) = O(n^2)$ , med vitnet $(c, n_0) = (4, 8)$ , og
ingenting mer. En øvre grense alene gir ikke $\Theta$ : den utelukker ikke at
algoritmen egentlig er ferdig på $\Theta(n)$ . For $\Theta(n^2)$ måtte du i tillegg
ha vist en nedre grense $c_1 n^2 \le T(n)$ .

Slik ser svaret ut på arket: a) definisjonen i én setning med kvantoren
tydelig. b) «Ja» og «Nei», hver med en halv linjes begrunnelse. c) « $O(n^2)$ —
bare øvre grense er vist.» Ikke mer.

📝Oppgave 6

Eksamensnivå, sjanger D

Skriv ned de formelle definisjonene av $O(g(n))$ ,
$\Omega(g(n))$ og $\Theta(g(n))$ , slik du ville gjort det på et ark uten
hjelpemidler.

Forklar deretter med én setning hvorfor $\Theta$ alltid er det svaret du bør gi
når du kan.

📝Oppgave 7

Eksamensnivå, sjanger A

Vis at $2n^2 + n\lg n = \Theta(n^2)$ ved å oppgi
eksplisitte konstanter, og avgjør deretter om uttrykket også er $o(n^3)$ og om
det er $\omega(n\lg n)$ .

📝Oppgave 8

Eksamensnivå, sjanger F

Et forslag til svar på et definisjonsspørsmål lyder
slik:

« $f(n) = o(g(n))$ betyr at det finnes en konstant $c > 0$ og en $n_0$ slik at
$f(n) < c\,g(n)$ for alle $n \ge n_0$ .»

a) Er dette definisjonen av $o$ ? Svar ja eller nei, og pek på nøyaktig hva
som er galt.
b) Hvilket symbol beskriver setningen faktisk?
c) Gi et konkret funksjonspar som setningen godtar, men som ikke er $o$ .

Begrepsbank

Begrepsbanken er flashcard- og repetisjonsstoff — den gjentar det du nettopp har
lest. Hopp trygt over ved førstegangslesing; tidsanslaget for kapitlet gjelder
kjernestoffet.

Intuisjonstabellen for de fem symbolene

O

Standard vekstordning

1 < \lg n < n < n\lg n < n^2 < n^3 < 2^n < n!

Transitivitet

f = O(g)

\Theta

som ekvivalensrelasjon

\Theta

Symmetriregelen mellom de løse symbolene

f(n) = O(g(n))

Strammeste grense

\Theta

Konstanter og lavere ordens ledd

5n^2 + 100n + 3000 = \Theta(n^2)

Logaritmens grunntall er en konstant

\log_b n = \lg n / \lg b

Kjøretidsfunksjonen

T(n)

T(n)

Beste, verste og forventet tilfelle

n

Polynomisk mot eksponentiell vekst

n^k

Hvorfor

O

alene ikke er nok

O

Repetisjonsoppgaver

Dette kapitlet er skrevet av Anthropics toppmodeller (Claude Opus og Claude Fable) og er foreløpig ikke manuelt gjennomgått — kvalitetskontrollen gjøres av uavhengige KI-agenter, og innmeldte feil rettes fortløpende. Funnet en feil? Meld fra, så retter vi den. Les mer om hvordan innholdet lages.

Skolesaga er en uavhengig læringsressurs og er ikke tilknyttet eller godkjent av Norges teknisk-naturvitenskapelige universitet. Dette er ikke offisielt studiemateriell. Les mer.