1.1 Asymptotisk notasjon — O (og kort Ω, Θ)

O-notasjonen (øvre grense) som IN2010s arbeidshest, med kort omtale av Ω og Θ — grunnlaget alle kjøretidssvar hviler på.

45 min

6 oppgaver

Asymptotisk notasjonO (og kort Ω

Din fremgang i kapitlet

0 / 6 oppgaver

Kapitlets plass i kurset

Brukes videre i

1.2Kjøretidsanalyse fra kode — løkketelling 1.4Kjøretids- og teori-fakta — sant/usant og antigjettings-strategi

Dette kapitlet er språket resten av boka snakker. To oppgavetyper hviler direkte
på det, og begge har dukket opp i alle sju settene (100 %):

- Sjanger B — kjøretid fra kode, altså at du får en kodesnutt og skal svare
med ett $O$ -uttrykk. Selve tellingen lærer du i
kap. 1.2; her lærer du hva svaret betyr.
- Sjanger C — kjøretids- og teorifakta, altså sant/usant-punkter om hvor
raskt noe går. Disse ligger på Del 1 av settet, som rettes automatisk og er
skalert mot gjetting.

Dette har derfor høyeste prioritet i hele boka: det må sitte, ikke fordi
kapitlet er verdt mange poeng i seg selv, men fordi hvert eneste kjøretidssvar
resten av eksamen bygger på det.

To avgrensninger sparer deg for arbeid. IN2010 bruker nesten utelukkende
$O$ ; $\Omega$ og $\Theta$ nevnes kort her og går knapt igjen i oppgavene, og
lillebrødrene $o$ og $\omega$ brukes overhodet ikke. Og kjøretid forenkles i
dette faget ved å telle løkker — ikke ved å sette opp rekurrensligninger,
som ikke er IN2010-pensum.

Forkunnskaper

Dette kapitlet kan leses uten forkunnskaper fra resten av boka — det er
startpunktet.

Har du aldri møtt $O$ -notasjon før, kan disse to gi et mykere første møte:

- Algoritmedefinisjon, pseudokode og kompleksitet (Big-O)
— samme idé, forklart uten eksamenspress.
- Potenser og logaritmer — hvis $\log_2 n$ føles ukjent. Du
trenger bare én ting derfra: at $\log_2 n$ er svaret på spørsmålet «hvor mange
ganger kan jeg halvere $n$ før jeg er nede i 1?».

Notasjons- og pseudokodeliste

Hvorfor vi ikke måler i sekunder

Folkeregisteret i en mellomstor kommune har rundt 40 000 innbyggere. Du skal
skrive en funksjon som finner ut om en bestemt person står i registeret.

Du kan gjøre det på to måter. Du kan gå gjennom listen fra start og sammenligne
hver eneste rad — da må du i verste fall innom alle 40 000. Eller du kan, hvis
listen er sortert, slå opp på midten, se om du havnet for høyt eller for lavt,
og halvere søkeområdet: 40 000, 20 000, 10 000, og så videre. Det tar 16 steg.

Forskjellen er ikke at det ene programmet er «raskere skrevet». Forskjellen er
hvordan de to skalerer. Doble registeret til 80 000, og den første metoden
bruker dobbelt så lang tid, mens den andre bruker ett steg til. Ett eneste.

Det er dette $O$ -notasjonen fanger. Den måler ikke sekunder, for sekunder
avhenger av maskinen, programmeringsspråket og hvor travelt det er på
serveren. Den måler hvordan arbeidsmengden vokser når inputen vokser — og
det er en egenskap ved algoritmen selv, ikke ved maskinen den kjøres på.

Å si at noe er asymptotisk betyr nettopp «når $n$ blir stor». Det er en
uttalelse om oppførsel i det lange løp, ikke om et bestemt regnestykke.

Problemstørrelsen n

n

Asymptotisk kjøretid

n

Store O — øvre grense

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

De to bokstavene $c$ og $n_0$ er hele hemmeligheten bak at $O$ virker så
grovkornet. $c$ lar deg se bort fra faste faktorer: en algoritme som bruker
$5n$ steg og en som bruker $n$ steg er begge $O(n)$ , fordi du bare velger
$c = 5$ . Og $n_0$ lar deg se bort fra hva som skjer for små input: at en
kompleks algoritme er treg på tre elementer, betyr ingenting.

Dette er både styrken og svakheten. Styrken er at $O$ sier noe robust som
gjelder på enhver maskin. Svakheten er at $O$ ikke sier noe som helst om
hvilken av to algoritmer som er raskest på nettopp dine data.

✏️Eksempel 1: Vis at $3n + 7$ er $O(n)$

En algoritme bruker $f(n) = 3n + 7$ grunnsteg. Vis at $f(n) = O(n)$ ved å
oppgi en konstant $c$ og en terskel $n_0$ som oppfyller definisjonen.

Vi skal finne $c$ og $n_0$ slik at $3n + 7 \leq c \cdot n$ for alle
$n \geq n_0$ .

Prøv $c = 4$ . Da må vi ha $3n + 7 \leq 4n$ , altså $7 \leq n$ . Det stemmer for
alle $n \geq 7$ .

Svar: med $c = 4$ og $n_0 = 7$ er $3n + 7 \leq 4n$ for alle $n \geq 7$ ,
og dermed er $3n + 7 = O(n)$ .

Kontroller gjerne: for $n = 7$ er venstresiden $28$ og høyresiden $28$ ; for
$n = 10$ er de $37$ og $40$ ; for $n = 100$ er de $307$ og $400$ . Avstanden
vokser, aldri motsatt.

Legg merke til at valget ikke er entydig. $c = 10$ og $n_0 = 1$ virker også.
Definisjonen krever bare at det finnes ett par som virker, ikke at du
finner det beste.

📝Oppgave 1

(Innstegsoppgave, sjanger C — kjøretidsfakta, altså et sant/usant-punkt om hvor
raskt noe går.) Avgjør om hvert utsagn er sant eller usant, og begrunn med én
setning.

a) $2n + 100$ er $O(n)$ .
b) $n^2$ er $O(n)$ .
c) $n$ er $O(n^2)$ .

De to andre bokstavene

$O$ har to søsken. Du trenger dem sjelden på IN2010-eksamen, men de dukker opp i
emnebeskrivelsen og i pensumboka, og det er verdt å kunne skille dem fra
hverandre på et sant/usant-punkt.

Omega — nedre grense

f(n) = \Omega(g(n))

Theta — tett grense

f(n) = \Theta(g(n))

Notasjonen IN2010 ikke bruker

o

✏️Eksempel 2: $O$, $\Omega$ eller $\Theta$?

En algoritme bruker $f(n) = n^2 + 5n + 3$ grunnsteg. Hvilke av disse utsagnene
er sanne?

a) $f(n) = O(n^2)$
b) $f(n) = O(n^3)$
c) $f(n) = \Omega(n)$
d) $f(n) = \Theta(n)$

a) Sant. Med

c = 9

n^2 + 5n + 3 \leq 9n^2

for alle

n \geq 1

(fordi

5n \leq 5n^2

3 \leq 3n^2

når

n \geq 1

). Dette er det
strammeste

O

-uttrykket, og det er dette du skal svare på eksamen.

b) Sant, men slapt. $n^2 \leq n^3$ for $n \geq 1$ , så en øvre grense på
$n^3$ holder også. Sensor ber om det strammeste uttrykket; svarer du $O(n^3)$
her, mister du poeng selv om påstanden i seg selv er sann.

c) Sant. $f(n) \geq n$ for alle $n \geq 1$ , så $n$ er en gyldig nedre
grense — også den slapp, men gyldig.

d) Usant. $\Theta(n)$ ville krevd at $f$ også er $O(n)$ , og det er den
ikke: $n^2$ -leddet vokser raskere enn noen fast faktor ganger $n$ . Den riktige
tette grensen er $\Theta(n^2)$ .

Momentet å ta med videre: $O$ er en øvre grense og har lov til å være
romslig. Derfor er «er dette $O(\ldots)$ ?» et annet spørsmål enn «hva er
kjøretiden?». Eksamen spør nesten alltid om det siste, og forventer det
strammeste uttrykket.

📝Oppgave 2

Sjanger C

Sant eller usant? Begrunn hvert svar med én setning.

a) Hvis $f(n) = \Theta(n \log n)$ , så er $f(n) = O(n^2)$ .
b) Hvis $f(n) = O(n)$ , så er $f(n) = \Theta(n)$ .
c) En algoritme som er $\Omega(n^2)$ kan ikke ha kjøretid $O(n)$ .

📜Vekstordningen

For store nok

n

gjelder alltid denne rekkefølgen:

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

Hvert uttrykk vokser raskere enn alle som står til venstre for det. Rekkefølgen
er den mest brukte enkeltopplysningen i hele faget, og den skal sitte utenat:
den avgjør hvilket ledd som dominerer i en sum, hvilken algoritme som er best i
en poengtrapp, og hva som er riktig svar på et sant/usant-punkt.

Konsekvensen for forenkling: i en sum er det alltid det raskest voksende
leddet som bestemmer $O$ -klassen. $n^2 + 1000n + 10^6$ er $O(n^2)$ , fordi de to
siste leddene til slutt er forsvinnende små ved siden av det første.

Dominerende ledd

O

Skjulte konstanter

O

✏️Eksempel 3: Sortér etter vekst og forenkl

Sortér disse fem uttrykkene fra saktest til raskest voksende, og oppgi det
strammeste

O

-uttrykket for hvert:

$4n^2 + 3n, \qquad 200, \qquad n \log n + 5n, \qquad 2^n + n^{10}, \qquad 7n + \log n$

Vi tar dem ett om gangen og finner det dominerende leddet i hver.

- $200$ er en konstant: ingen $n$ i det hele tatt, altså $O(1)$ .
- $7n + \log n$ : siden $\log n < n$ , dominerer $7n$ , og konstanten faller bort.
Altså $O(n)$ .
- $n \log n + 5n$ : her er $n \log n$ det største leddet, fordi $\log n > 1$ for
$n > 2$ . Altså $O(n \log n)$ .
- $4n^2 + 3n$ : kvadratleddet dominerer, konstanten 4 faller bort. Altså $O(n^2)$ .
- $2^n + n^{10}$ : dette er den som lurer flest. $n^{10}$ ser voldsomt ut, men
$2^n$ passerer den — allerede rundt $n = 59$ er $2^n$ større, og deretter
drar den fra for godt. Altså $O(2^n)$ .

Rekkefølgen fra saktest til raskest voksende:

$200 \ \ <\ \ 7n + \log n \ \ <\ \ n\log n + 5n \ \ <\ \ 4n^2 + 3n \ \ <\ \ 2^n + n^{10}$

altså $O(1)$ , $O(n)$ , $O(n \log n)$ , $O(n^2)$ , $O(2^n)$ .

Merk framgangsmåten, for den er den samme hver gang: finn det dominerende
leddet, stryk konstanten foran det, og skriv $O$ av det som står igjen. Ingen
tredje ting.

📝Oppgave 3

Sjanger B

Oppgi det
strammeste $O$ -uttrykket for hvert av disse.

a) $6n^3 + 400n^2 + 9$
b) $50$
c) $n + n + n + n$
d) $n^2 \log n + n^2$

Fella som kommer igjen hvert år

Det finnes ett sant/usant-punkt som går igjen i settene i ulike forkledninger,
og som svært mange svarer feil på. Det ser slik ut:

«En algoritme med bedre asymptotisk kompleksitet bruker alltid færre
grunnsteg enn en med dårligere kompleksitet, på samme input.»

Svaret er usant, og grunnen ligger i de to bokstavene $c$ og $n_0$ fra
definisjonen.

📜Bedre asymptotikk gir ikke færre steg for all input

At $f(n) = O(n \log n)$ og $g(n) = O(n^2)$ sier kun at det finnes en
terskel $n_0$ der $f$ havner under $g$ og blir liggende der. Det sier ingenting
om hvem som er minst før den terskelen.

Et konkret par: la $f(n) = 1000\,n \log n$ og $g(n) = n^2$ . For $n = 100$ er
$f(100) \approx 664\,000$ mens $g(100) = 10\,000$ — den «bedre» algoritmen
bruker over seksti ganger så mange steg. Først rundt $n = 14\,000$ tar $f$ igjen
$g$ , og fra da av vinner den for alltid.

Dette er grunnen til at praktiske sorteringsbiblioteker bytter til
innsettingssortering for korte lister, selv om den er $O(n^2)$ : på små input er
den faktisk raskest.

Formuleringen du skal kjenne igjen: «bedre $O$ » betyr «vinner til slutt»,
ikke «vinner alltid».

Bedre asymptotikk er ikke færre steg

O

✏️Eksempel 4: Sant/usant på eksamensnivå

Marker sant eller usant, og begrunn hvert svar med én setning.

a) En $O(n \log n)$ -algoritme bruker alltid færre grunnsteg enn en
$O(n^2)$ -algoritme på samme input.

b) Et array kan sjekkes for om det er sortert i $O(n)$ .

c) Hvis en algoritme har kjøretid $O(n)$ , kan den ikke ha kjøretid
$O(n^2)$ .

a) Usant.

O

-klassen sier bare hva som skjer for store nok

n

; en
skjult konstant kan gjøre den asymptotisk bedre algoritmen tregere på små input.

b) Sant. Gå gjennom arrayet én gang og sammenlign hvert element med det
neste; du er ferdig etter $n-1$ sammenligninger, altså $O(n)$ . Pseudokoden står
rett under her.

c) Usant. $O$ er en øvre grense, og en øvre grense kan gjøres
slappere. Alt som er $O(n)$ er også $O(n^2)$ — det er bare et mindre
informativt svar. Denne formuleringen er en klassisk felle fordi den høres
fornuftig ut.

Sensorblikket: på slike punkter er det ordet «alltid» i (a) og ordet «kan
ikke» i (c) som avgjør. Les sant/usant-utsagn ord for ord — det er den mest
gjentatte oppfordringen i sensorveiledningene.

📜Pseudokode-kontrakt: `IsSorted`

Antagelser om representasjon. A er et array med

n

elementer, indeksert
fra 0, slik at A[0] er det første og A[n-1] det siste. Elementene kan
sammenlignes med < og >.

Prebetingelse: A inneholder $n \geq 0$ elementer.
Postbetingelse: prosedyren returnerer true hvis og bare hvis
A[0] <= A[1] <= ... <= A[n-1]; arrayet er uendret.

Procedure IsSorted(A)
  Input:  array A med n elementer, indeksert fra 0
  Output: true hvis A er sortert stigende, ellers false
  n = A.length
  for i = 0 to n-2:
      if A[i] > A[i+1]:
          return false
  return true

Grunnidé i én setning: et array er sortert nøyaktig når ingen nabopar står i
gal rekkefølge, så det holder å sjekke naboparene.

Kjøretid: løkka går høyst $n-1$ runder og gjør konstant arbeid i hver, så
kjøretiden er $O(n)$ . Merk at den kan avslutte langt tidligere — finner den et
feil nabopar med én gang, stopper den etter én runde. Men $O$ beskriver det
verste tilfellet, og verst er at hele arrayet faktisk er sortert.

📝Oppgave 4

Sjanger C

Se på pseudokoden for IsSorted over.

a) Hva er kjøretiden i verste tilfelle, og hvilken input gir det verste
tilfellet?
b) Hva er kjøretiden i beste tilfelle, og hvilken input gir det?
c) Er det riktig å si at IsSorted er $O(n^2)$ ?

Verste, beste og forventet tilfelle

Oppgaven IsSorted viste at samme algoritme kan bruke svært ulik tid på ulik
input av samme størrelse. Derfor må du vite hvilket tilfelle du snakker om.

Hovedregelen i IN2010: oppgir du en kjøretid uten å presisere, mener du
verste tilfelle. Unntaket er noen få strukturer der forventet tilfelle er det
interessante, og der sier oppgaven det uttrykkelig — hashtabellen er det
viktigste eksempelet, og den kommer i Del 3.

Verste tilfelle

n

Forventet tilfelle

O(1)

Beste tilfelle

n

Typiske feil

Fire feil koster poeng på nettopp dette stoffet, år etter år.

- Å tro at bedre $O$ betyr færre steg for all input. Det er faktisk feilen
som går igjen oftest, og den har sitt eget sant/usant-punkt nesten hvert år.
$O$ handler om store $n$ , punktum.
- Å blande øvre og tett grense. $3n + 7$ er $O(n^2)$ (sant, men slapt) og
$\Theta(n)$ (presist). Er du bedt om kjøretiden, gi det strammeste $O$ -svaret.
- Å bruke $o$ eller $\omega$ . De finnes ikke i IN2010. Svar med $O$ .
- Å ta med konstanter og lavere ordensledd i svaret. «Kjøretiden er
$O(3n^2 + 5n)$ » er ikke et galt regnestykke, men det er feil form: svaret
skal være $O(n^2)$ .

Og en femte, som strengt tatt hører til hele faget: å bruke $n$ uten å si hva
$n$ er (dette er felle #10 i bokas register — å drøfte eller oppgi
kjøretid uten å definere problemstørrelsen). Én setning holder: « $n$ er antall
elementer i arrayet».

📝Oppgave 5

Sjanger C, eksamensnivå

Du sammenligner to programmer som løser samme
oppgave. Program P bruker $f(n) = 2n^2$ grunnsteg, program Q bruker
$g(n) = 500n$ grunnsteg.

a) Oppgi $O$ -klassen for hvert program.
b) For hvilke $n$ er P faktisk raskest?
c) En kollega sier: «Q har best kompleksitet, så vi bruker Q.» Datasettene
deres har alltid rundt 50 elementer. Hva svarer du?

📝Oppgave 6

Sjanger C, eksamensnivå

Avgjør sant eller usant, og begrunn hvert svar med én
setning.

a) $n \log n = O(n^2)$ .
b) $2^{n+1} = O(2^n)$ .
c) $n! = O(2^n)$ .
d) Hvis $f(n) = O(g(n))$ og $g(n) = O(h(n))$ , så er $f(n) = O(h(n))$ .

En liten notasjonsvane du bør kjenne

IN2010 skriver $f(n) = O(g(n))$ med likhetstegn, slik denne boka har gjort hele
veien. Strengt tatt er $O(g)$ en mengde av funksjoner, og det logisk
korrekte ville vært « $f$ tilhører $O(g)$ ». Likhetstegnet er en gammel og fast
konvensjon i faget, og det er den formen du møter i oppgavetekster.

Praktisk betyr det bare én ting: likhetstegnet går ikke begge veier. Du kan
skrive $3n + 7 = O(n)$ , men ikke $O(n) = 3n + 7$ . Les det som «er» eller
«tilhører», ikke som «er lik».

Likhetstegnet i f(n) = O(g(n))

f

De sju klassene du møter i dette faget

Nesten alle kjøretider i IN2010 lander i en av disse. Tabellen er verdt å kunne
utenat, både veien fra navn til uttrykk og veien fra uttrykk til et eksempel.

$O$ -klasse	Navn	Typisk eksempel	Hva som skjer når $n$ dobles
$O(1)$	konstant	slå opp `A[5]`, legge til bakerst i et array	ingenting
$O(\log n)$	logaritmisk	binærsøk i et sortert array	ett steg til
$O(n)$	lineær	gå gjennom hele arrayet én gang	dobbelt så mye arbeid
$O(n \log n)$	lineærlogaritmisk	flettesortering, heapsortering	litt mer enn dobbelt
$O(n^2)$	kvadratisk	sammenligne alle par, boblesortering	fire ganger så mye
$O(n^3)$	kubisk	tre nøstede løkker over samme mengde	åtte ganger så mye
$O(2^n)$	eksponentiell	prøve alle delmengder	kvadrering av arbeidet

Den siste kolonnen er den mest nyttige på eksamen: den lar deg kontrollere et
svar på fem sekunder. Har du regnet ut at en algoritme er

O(n^2)

, men vet at
den bare bruker ett steg til når inputen dobles, har du regnet feil et sted.

Konstant tid

O(1)

Logaritmisk tid

O(\log n)

Lineær tid

O(n)

Lineærlogaritmisk tid

O(n \log n)

Kvadratisk tid

O(n^2)

Kubisk tid

O(n^3)

Eksponentiell tid

O(2^n)

Repetisjon — kapitlet i åtte punkter

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 Universitetet i Oslo. Dette er ikke offisielt studiemateriell. Les mer.