1.3 DRILL — Asymptotisk forenkling og notasjon

Systematisk drill i sjanger A: definér symbolene, klassifisér funksjoner og forenkl sammensatte uttrykk til det strammeste svaret — de garanterte poengene.

80 min

14 oppgaver

DRILLAsymptotisk forenklingnotasjon

Din fremgang i kapitlet

0 / 14 oppgaver

Kapitlets plass i kurset

Bygger på

1.2Forenkling av asymptotiske uttrykk

Dette er et drillkapittel. Det lærer deg ingenting nytt — det gjør de grepene
du alt har sett til noe du utfører uten å tenke, under tidspress og uten
hjelpemidler.

Sjanger A — asymptotisk forenkling, altså at du får et sammensatt uttrykk og
skal koke det ned til ett strammeste svar, er den mest forutsigbare sjangeren i
hele faget. Den er med i 100 % (17 av de 17 settene i grunnlaget), ofte med
2–3 oppgaver i samme sett. Tett opptil ligger sjanger D — definisjonsspørsmålet,
der du blir bedt om å skrive ned den presise definisjonen av ett av de fem
symbolene $O$ , $\Omega$ , $\Theta$ , $o$ og $\omega$ . Begge sjangrene trenes i de
samme rundene her.

Høyeste prioritet — dette må sitte. Ingen andre poeng i faget er like
billige: oppgaveteksten er kort, svaret er ett uttrykk, og fasiten er entydig.

Slik er kapitlet lagt opp. Først løsningsoppskriften, så ett fullt
gjennomarbeidet eksamenscase med margnotater om hva som gir uttelling ved hvert
steg. Deretter 14 oppgaver på eksamensnivå som roterer gjennom alle variantene:
definér et symbol, klassifisér en funksjon, forenkl en sum, håndtér blandede
operatorer og regn på brøkuttrykk. Alle har full løsning og hint.

Kapitlet er anslått til 80 minutter og kan trygt deles over flere økter. Det
står «— naturlig pausepunkt —» der det er et godt sted å stoppe, og hver
overskrift har sitt eget tidsanslag.

To ord om eksamensformen før vi begynner. En kortsvarsoppgave er en oppgave
der du skriver svaret selv, i en liten rute, uten å krysse av. Delvis
uttelling betyr at et svar som er delvis riktig kan gi noen av poengene — det
lønner seg altså å skrive ned det du er sikker på. I settene fra 2015 til 2018
sto det svart på hvitt på oppgavearket: lange svar teller ikke positivt. Det er
en god rettesnor her. Ett riktig uttrykk er hele svaret.

Forkunnskaper

Dette kapitlet er ren trening på stoffet fra de to foregående kapitlene og
introduserer ingenting nytt. Du bør ha vært gjennom:

- Kapittel 1.1, Asymptotisk notasjon — de fem symbolene. Der står de formelle
definisjonene av $O$ , $\Omega$ , $\Theta$ , $o$ og $\omega$ med konstantene $c$
og $n_0$ , og den standard vekstordningen
$1 < \lg n < n < n\lg n < n^2 < n^3 < 2^n < n!$ .
- Kapittel 1.2, Forenkling av asymptotiske uttrykk. Der står de tre
forenklingsreglene: i en sum dominerer det raskest voksende leddet, en
$\Omega$ - eller $\omega$ -term uten øvre grense fjerner enhver $O$ -grense for
hele summen, og svaret skal alltid være det strammeste enkeltuttrykket.

Ordet asymptotisk betyr «for store $n$ ». Vi bryr oss ikke om hvordan
funksjonen oppfører seg for $n = 5$ , bare om hvordan den vokser når $n$ blir
vilkårlig stor. Alle konstanter og alle lavere ordens ledd faller derfor bort.

Trenger du et mykere første møte med vekstklasser og $O$ -notasjon før du drilles
på dem, er dette et godt sted å begynne:

- Algoritmedefinisjon, pseudokode og kompleksitet (Big-O)
— NTNUs eget introduksjonsemne i programmering, der $O$ -notasjonen forklares
på kode som faktisk kjører.

Notasjonen i denne boka følger CLRS (Cormen, Leiserson, Rivest og Stein,
Introduction to Algorithms), som er pensumankeret i faget. Det er derfor det
står $\lg n$ og ikke $\log n$ i uttrykkene: $\lg n$ betyr $\log_2 n$ .

Notasjons- og pseudokodeliste

Slik ser sjanger A ut på arket (~10 min)

Oppgaven er alltid av samme type. Du får et uttrykk som er satt sammen av flere
ledd, hvert ledd merket med ett av de fem symbolene, og du blir bedt om å skrive
det som ett uttrykk — det strammeste som er sant.

Det som gjør oppgaven forutsigbar, er at du aldri skal bevise noe. Du skal ikke
finne $c$ og $n_0$ , ikke tegne grafer og ikke skrive en utledning. Du skal
gjenkjenne hvilket ledd som vokser raskest, og hvilke av leddene som har en
øvre grense og hvilke som ikke har det.

Det som gjør oppgaven farlig, er at det finnes mange sanne svar, og bare ett
av dem gir full uttelling. At $3n^2 + 5n$ er $O(n^{10})$ er helt sant, men det er
et dårlig svar: det strammeste er $\Theta(n^2)$ . Løsningsforslagene er tydelige
på at det er det strammeste uttrykket som etterspørres.

📜Løsningsoppskriften for sjanger A

Kjør denne ovenfra og ned, hver gang — også når svaret virker opplagt.

1. Identifisér hvert ledd og dets vekstklasse. Skriv leddene under hverandre
og sett vekstklassen på hvert enkelt: er dette $n^2$ , $n^2\lg n$ eller $n^3$ ?
2. For summer: behold det raskest voksende leddet. Alt som vokser
langsommere, forsvinner. Sjekk deretter om en $\omega$ - eller $\Omega$ -term
fjerner den øvre grensen for hele summen.
3. For grenser hver for seg: oppgi strammeste $\Omega$ og strammeste $O$
separat. Ber oppgaven om både nedre og øvre grense, skal du gi to uttrykk —
og de er ofte ikke like.
4. For brøk: bytt teller og nevner med sin ekstremverdi, og forkort. Et
$\Theta$ -ledd har både en største og en minste verdi; et $O$ -ledd har bare en
største; et $\Omega$ -ledd har bare en minste.
5. Skriv kun det strammeste enkeltuttrykket. Ett uttrykk, ingen utledning,
ingen forklaring — med mindre oppgaven uttrykkelig ber om en.

Punkt 4 fortjener en presisering, for det er der de fleste bommer. Et symbol
inne i et regnestykke står for en vilkårlig funksjon i den klassen. Når du
spør «hvor stor kan brøken bli?», velger du den største lovlige telleren og den
minste lovlige nevneren. Når du spør «hvor liten kan den bli?», velger du
motsatt. Har en av dem ingen slik ekstremverdi, finnes ikke den grensen.

✏️Eksempel 1: Et fullt eksamenscase, steg for steg

Et sett gir deg tre deloppgaver om det samme uttrykket:

$S(n) = \frac{\Theta(n^6)}{\Omega(n^2)} + \Theta(n^3\lg n) + o(n^4)$

a) Gi den strammeste øvre grensen for $S(n)$ .

b) Gi den strammeste nedre grensen for $S(n)$ .

c) Kan $S(n)$ skrives som ett $\Theta$ -uttrykk? Begrunn med én setning.

Steg 1 — identifisér leddene og grensetypen deres.

Ledd	Øvre grense?	Nedre grense?
$\displaystyle \frac{\Theta(n^6)}{\Omega(n^2)}$	ja (regnes ut i steg 2)	nei
$\Theta(n^3\lg n)$	ja	ja
$o(n^4)$	ja, og den er ikke oppnådd	nei

Margnotat: Selve oppsettet er verdt uttelling. Skriver du opp leddene med
hver sin grensetype før du regner, gjør du sjelden feil på hvilken
ekstremverdi som skal brukes hvor. Det tar femten sekunder.

Steg 2 — regn ut brøkleddet for seg. Telleren er

\Theta(n^6)

, altså klemt

mellom $c_1 n^6$ og $c_2 n^6$ . Nevneren er $\Omega(n^2)$ , altså minst $c\,n^2$ ,
men uten noen øvre grense — den kan like gjerne være $n^{10}$ .
Størst mulig verdi av brøken får du med størst mulig teller og minst mulig

nevner:
$\frac{c_2 n^6}{c\,n^2} = \frac{c_2}{c}\,n^4$
Brøkleddet er altså $O(n^4)$ . Minst mulig verdi finnes derimot ikke: nevneren

kan vokse uten grense, og da går brøken mot null. Brøkleddet har ingen nedre
grense.

Margnotat: Her faller delpoenget for de fleste. Hopper du over å bytte inn
ekstremverdiene og skriver $\Theta(n^4)$ rett fra $6 - 2 = 4$ , har du behandlet
en $\Omega$ -nevner som om den var en $\Theta$ -nevner. Svaret ser riktig ut og
er galt.

Steg 3 — a) den strammeste øvre grensen. Alle tre leddene har en øvre
grense: brøkleddet er $O(n^4)$ , midtleddet er $O(n^3\lg n)$ , og $o(n^4)$ er i
særdeleshet $O(n^4)$ . Det raskest voksende av disse er $n^4$ .
$S(n) = O(n^4)$

Margnotat: Legg merke til at $o(n^4)$ ikke løfter svaret over $n^4$ .
Symbolet $o$ betyr strengt langsommere enn $n^4$ ; det er en øvre grense, ikke
en nedre.

Steg 4 — b) den strammeste nedre grensen. Bare midtleddet har en nedre

grense: $\Theta(n^3\lg n)$ er minst $c_1 n^3\lg n$ . De to andre leddene er
ikke-negative og kan bare gjøre summen større.
$S(n) = \Omega(n^3\lg n)$

Margnotat: Fristelsen er å skrive $\Omega(n^4)$ fordi $n^4$ dukket opp i
a). Men ingen av leddene garanterer $n^4$ nedenfra — brøkleddet kan være
forsvinnende lite.

Steg 5 — c) kan det skrives som ett $\Theta$ -uttrykk?

Nei. Den øvre grensen er $n^4$ og den nedre er $n^3\lg n$ , og de to møtes ikke:
$n^3\lg n = o(n^4)$ . Brøkleddet kan legge seg hvor som helst i mellomrommet
avhengig av hvilken nevner som velges, og da finnes det ingen felles $\Theta$ .

Margnotat: «Nei, fordi øvre og nedre grense ikke møtes» er hele svaret på
c). En utledning på seks linjer gir ikke mer.

Kortsvaret du faktisk leverer:
a)

O(n^4)

\Omega(n^3\lg n)

c) Nei — grensene møtes ikke,

siden $n^3\lg n = o(n^4)$ .

Symbolene skal kunne skrives ned kaldt (~12 min)

— naturlig pausepunkt —

Definisjonsspørsmålet er den ene oppgaven i faget der du ikke kan resonnere deg
fram til svaret. Enten kan du formen med $c$ og $n_0$ , eller så kan du den ikke.
Fordi eksamen er uten hjelpemidler, må de fem definisjonene sitte som utenatlære.

De tre første har samme skjelett — «det finnes konstanter … slik at … for alle
$n \ge n_0$ » — og skiller seg bare i hvilken vei ulikheten peker. De to siste
bytter ut «det finnes en $c$ » med «for alle $c$ », og det er hele forskjellen.

📝Oppgave 1

Eksamensnivå, sjanger D

a) Definér

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

presist, med de konstantene som inngår.

b) Definér $f(n) = \Omega(g(n))$ presist.

c) Hvilket ord i disse to definisjonene er det som gjør at du bare trenger å
finne én konstant $c$ som virker?

📝Oppgave 2

Eksamensnivå, sjanger D

a) Definér

f(n) = o(g(n))

presist.

b) Definér $f(n) = \omega(g(n))$ presist.

c) Forklar med én setning hva som skiller $o$ fra $O$ , og gi ett konkret
funksjonspar der $f(n) = O(g(n))$ er sant, men $f(n) = o(g(n))$ er galt.

Kvantoren, og ingenting annet. Et svar som skriver «det finnes en $c$ » i
definisjonen av $o$ , er galt selv om resten er ordrett riktig — og det er den
enkeltfeilen som oftest koster hele poenget i sjanger D.

Et huskegrep: $O$ og $\Omega$ er de romslige symbolene og trenger bare én
konstant. $o$ og $\omega$ er de strenge symbolene og krever at alle
konstanter virker.

📝Oppgave 3

Eksamensnivå, sjanger D

a) Definér

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

presist.

b) Forklar med én setning forskjellen mellom $\Theta(g(n))$ og $O(g(n))$ .

c) En besvarelse skriver: « $\Theta$ betyr at $f$ og $g$ vokser like fort, og
$O$ betyr at $f$ vokser saktere enn $g$ .» Hva er galt i den siste halvdelen?

Å klassifisere en funksjon (~12 min)

Den andre faste varianten gir deg en konkret funksjon og en konkret $g(n)$ , og
spør hvilke av de fem symbolene som stemmer. Framgangsmåten er alltid den samme:
se på forholdet $f(n)/g(n)$ når $n$ vokser.

- Forholdet stabiliserer seg på et positivt tall: $f = \Theta(g)$ , og dermed
både $O(g)$ og $\Omega(g)$ .
- Forholdet går mot null: $f = o(g)$ , og dermed $O(g)$ , men ikke $\Omega(g)$ .
- Forholdet vokser uten grense: $f = \omega(g)$ , og dermed $\Omega(g)$ , men
ikke $O(g)$ .

Merk deg de to «og dermed»-ene. De gir gratis delpoeng: har du først avgjort at
noe er $o(g)$ , kan du uten videre svare ja på om det er $O(g)$ .

✏️Eksempel 2: Fire spørsmål om samme funksjon

La $f(n) = 4n^2\lg n$ . Avgjør for hver av påstandene om den er sann eller
usann, og oppgi til slutt den strammeste enkeltpåstanden du kan gjøre om $f$ .

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

Regn ut forholdene, ett om gangen.

a) Sann. $\dfrac{4n^2\lg n}{n^3} = \dfrac{4\lg n}{n}$ , som går mot null. Går
forholdet mot null, er $f = o(n^3)$ , og alt som er $o$ er også $O$ .

b) Usann. $\dfrac{4n^2\lg n}{n^2} = 4\lg n$ , som vokser uten grense.
Forholdet stabiliserer seg ikke, så $f$ er ikke $\Theta(n^2)$ . Den er $\Omega(n^2)$ ,
men ikke $O(n^2)$ .

c) Sann. Samme regnestykke som i b): forholdet $4\lg n$ vokser uten grense,
og det er nettopp definisjonen av $\omega$ .

d) Sann — det er den samme observasjonen som i a), sagt strengere.

Strammeste enkeltpåstand: $f(n) = \Theta(n^2\lg n)$ . Konstanten 4 forsvinner,
og både øvre og nedre grense er $n^2\lg n$ .

Legg merke til at både $O(n^3)$ og $\Omega(n^2)$ er sanne påstander om $f$ , men
begge kaster bort informasjon. Blir du bedt om den strammeste, er det bare
$\Theta(n^2\lg n)$ som gir full uttelling.

📝Oppgave 4

Eksamensnivå, sjanger A

La $f(n) = 2n^3 + 7n^2$ .

a) Er $f(n) = \Theta(n^3)$ ?

b) Er $f(n) = O(n^4)$ ? Er den $o(n^4)$ ?

c) Er $f(n) = \omega(n^2)$ ?

d) Oppgi den strammeste enkeltpåstanden om $f(n)$ .

📝Oppgave 5

Eksamensnivå, sjanger A

Avgjør hver påstand, og begrunn hver med
forholdet $f(n)/g(n)$ .

a) $n\lg^2 n = O(n^2)$ ?

b) $n\lg^2 n = \Theta(n\lg n)$ ?

c) $\lg(n^3) = \Theta(\lg n)$ ?

d) $\sqrt{n} = \omega(\lg n)$ ?

Typiske feil

Tre feil står for nesten alle tapte poeng i denne sjangeren. De to første er
gamle kjenninger; den tredje er den dyreste.

Felle #4 — å oppgi en løsere grense når en strammere finnes. Du regner
riktig, konkluderer med $O(n^3)$ , og det er sant — men $\Theta(n^2)$ var også
sant og er strammere. Løsningsforslagene ber om det strammeste uttrykket, og et
sant, løsere svar gir sjelden full uttelling. Rutinen som fjerner fellen: når du
har funnet en $O$ -grense, spør alltid om den samme funksjonen også er $\Omega$ av
det samme. Er den det, skriv $\Theta$ .

Feil kvantor i $o$ og $\omega$ . Definisjonene av $O$ og $\Omega$ sier «det
finnes en $c$ »; definisjonene av $o$ og $\omega$ sier «for alle $c$ ». Blander du
dem, blir definisjonssvaret galt selv om du har forstått innholdet, og du får
også klassifiseringsoppgavene feil: du kommer til å svare $o(n^2)$ om noe som
bare er $O(n^2)$ .

Å behandle en brøk som ett ledd. Dette er den dyreste. Ser du
$\dfrac{\Theta(n^5)}{\Omega(n^2)}$ og trekker fra eksponentene til $\Theta(n^3)$ ,
har du antatt at nevneren er $\Theta(n^2)$ — men $\Omega$ har ingen øvre grense,
og nevneren kan være vilkårlig stor. Riktig svar er $O(n^3)$ , uten nedre grense.
Regelen er å bytte teller og nevner med hver sin ekstremverdi før du
forkorter, aldri etterpå.

Summer: ett ledd overlever (~12 min)

— naturlig pausepunkt —

I en sum av asymptotiske ledd er det bare det raskest voksende leddet som
betyr noe. De andre er så små at de kan puttes inn i konstanten. Men før du
skriver ned svaret, må du stille ett spørsmål til: har hele summen en øvre
grense?

Svaret er nei så snart minst ett ledd er merket $\Omega$ eller $\omega$ . Et slikt
ledd står for en funksjon som er bundet nedenfra og fri oppover, og en sum som
inneholder en fri funksjon kan ikke bindes ovenfra. Da er svaret et
$\Omega$ - eller $\omega$ -uttrykk, ikke et $\Theta$ -uttrykk.

Og motsatt: er alle leddene $O$ , $\Theta$ eller $o$ , har summen en øvre grense.
Har den i tillegg minst ett $\Theta$ -ledd som er det raskest voksende, er svaret
et $\Theta$ -uttrykk.

📝Oppgave 6

Eksamensnivå, sjanger A

Forenkl til ett strammeste uttrykk:

$\Theta(n^2\lg n) + O(n^2) + \Theta(n\lg^2 n)$

📝Oppgave 7

Eksamensnivå, sjanger A

Forenkl til ett strammeste uttrykk:

$\Theta(n^3) + \Omega(n^2) + O(n\lg n)$

📝Oppgave 8

Eksamensnivå, sjanger A

Forenkl til ett strammeste uttrykk, og forklar
med én setning hvorfor du ikke kan skrive

\omega

i svaret:

$O(n^4) + \omega(n^2) + \Theta(n^3)$

At du ikke overdriver. Fristelsen er å la det sterkeste symbolet i uttrykket
smitte over på svaret: det står $\omega$ i oppgaven, altså må det stå $\omega$ i
svaret. Slik er det ikke. $\omega(n^2)$ lover bare at leddet er strengt raskere
enn $n^2$ — det lover ingenting om $n^3$ .

Regelen som holder: et $\omega(g)$ -ledd fjerner den øvre grensen, men det løfter
bare den nedre grensen til $g$ selv, ikke til noe over $g$ .

Grenser hver for seg (~10 min)

Noen oppgaver ber ikke om ett uttrykk, men om to: den strammeste nedre og
den strammeste øvre grensen, hver for seg. Det er en gavepakke, for den varianten
er lettere enn den vanlige — du slipper å avgjøre om grensene møtes.

Framgangsmåten er å gå gjennom leddene to ganger. Første runde: hvilke ledd har
en nedre grense, og hvilken av dem er størst? Andre runde: hvilke ledd har en
øvre grense, og hvilken av dem er størst? Har ett av leddene ingen øvre grense,
er svaret på andre runde at det ikke finnes noen.

At de to svarene ofte er forskjellige, er selve poenget med spørsmålsformen.

✏️Eksempel 3: To grenser som ikke møtes

Oppgi den strammeste nedre og den strammeste øvre grensen, hver for seg, for

$n\lg n + \Theta(n^2) + O(n^2\lg n)$

Nedre grense. Hvilke ledd garanterer noe nedenfra? Det første leddet er en
konkret funksjon,

n\lg n

, som alltid er der. Det andre er

\Theta(n^2)

, som er
minst

c_1 n^2

. Det tredje,

O(n^2\lg n)

, garanterer ingenting nedenfra — det
kan være så lite som null. Største garanti nedenfra er dermed

n^2

$\Omega(n^2)$

Øvre grense. Alle tre leddene har en øvre grense: $n\lg n$ er seg selv,
$\Theta(n^2)$ er høyst $c_2 n^2$ , og $O(n^2\lg n)$ er høyst $c_3 n^2\lg n$ . Det
raskest voksende av disse er $n^2\lg n$ :

$O(n^2\lg n)$

Kortsvaret: $\Omega(n^2)$ og $O(n^2\lg n)$ .

Grensene møtes ikke, og det skal de heller ikke — $O(n^2\lg n)$ -leddet kan legge
seg hvor som helst mellom null og $n^2\lg n$ . Å presse svaret inn i ett
$\Theta$ -uttrykk ville vært galt.

📝Oppgave 9

Eksamensnivå, sjanger A

Oppgi strammeste nedre og strammeste øvre grense,
hver for seg, for

$\Theta(n\lg n) + O(n^2) + \Theta(n)$

og si med én setning om uttrykket kan skrives som ett $\Theta$ -uttrykk.

📝Oppgave 10

Eksamensnivå, sjanger A

Oppgi strammeste nedre og strammeste øvre grense,
hver for seg, for

$\frac{O(n^4)}{\Theta(n)} + \Theta(n^2)$

Blandede operatorer (~10 min)

Den varianten som oftest ser verre ut enn den er, er den som blander alle fem
symbolene i samme sum. Oppskriften er likevel uendret, og den kan sammenfattes i
to spørsmål:

1. Er det noe her som ikke har øvre grense? Alle $\Omega$ - og $\omega$ -ledd
svarer ja. Da blir svaret et $\Omega$ - eller $\omega$ -uttrykk.
2. Hvilket ledd gir den sterkeste garantien nedenfra? Det bestemmer hvilken
funksjon som står inne i parentesen.

Er svaret på spørsmål 1 nei, faller du tilbake på den vanlige summeregelen: det
raskest voksende leddet vinner, og symbolet blir $\Theta$ hvis det leddet er et
$\Theta$ -ledd, ellers $O$ .

📝Oppgave 11

Eksamensnivå, sjanger A

Forenkl til ett strammeste uttrykk:

$O(n^2) + \Theta(n\lg n) + \omega(n\lg n) + o(n)$

📝Oppgave 12

Eksamensnivå, sjanger A

Forenkl hvert produkt til ett strammeste uttrykk:

a) $\Theta(n\lg n)\cdot O(n)$

b) $\omega(n)\cdot\Theta(n^2)$

c) $O(n^2)\cdot o(n)$

Om du husker at symbolene beskriver mengder av funksjoner, ikke tall.
$\Theta(n\lg n)\cdot O(n)$ er ikke «gang sammen to uttrykk», det er «velg en
vilkårlig funksjon fra hver mengde og gang dem sammen — hva kan resultatet bli?».

Når du tenker slik, følger regnereglene av seg selv: mangler den ene faktoren en
nedre grense, mangler produktet den også.

Brøkuttrykk — teller og nevner hver for seg (~14 min)

— naturlig pausepunkt —

Brøkvarianten er den som gir flest tapte poeng, og grunnen er at den ser ut som
vanlig potensregning. Fristelsen er å trekke eksponentene fra hverandre og gå
videre. Det virker bare når både teller og nevner er $\Theta$ -ledd.

Den trygge rutinen har tre linjer:

1. Spør: hvor stor kan brøken bli? Sett inn den største lovlige telleren og den
minste lovlige nevneren, og forkort. Får du et uttrykk, er det $O$ -grensen.
Har telleren ingen største verdi, eller nevneren ingen minste, finnes ingen
$O$ -grense.
2. Spør: hvor liten kan brøken bli? Sett inn den minste lovlige telleren og den
største lovlige nevneren, og forkort. Får du et uttrykk, er det
$\Omega$ -grensen. Ellers finnes den ikke.
3. Møtes svarene fra 1 og 2, skriv $\Theta$ . Ellers oppgir du det ene som finnes.

Tabellen du trenger for linje 1 og 2 er kort: $\Theta(g)$ har både største og
minste verdi (begge er $g$ opp til en konstant), $O(g)$ har bare største, og
$\Omega(g)$ har bare minste.

✏️Eksempel 4: Brøk og sum i samme uttrykk

Forenkl til ett strammeste uttrykk:

$\frac{\Theta(n^5\lg n)}{\Theta(n^2)} + O(n^3) + \Theta(n^2\lg^2 n)$

Brøkleddet. Både teller og nevner er

\Theta

-ledd, og det er det eneste
tilfellet der du trygt kan forkorte direkte. Største brøk:

\dfrac{c_2 n^5\lg n}{c_3 n^2} = \dfrac{c_2}{c_3}n^3\lg n

. Minste brøk:

\dfrac{c_1 n^5\lg n}{c_4 n^2} = \dfrac{c_1}{c_4}n^3\lg n

. Samme uttrykk begge
veier, altså

\Theta(n^3\lg n)

Sammenlign de tre leddene. Vi har nå $\Theta(n^3\lg n) + O(n^3) + \Theta(n^2\lg^2 n)$ . Sorter vekstklassene:

- $n^3\lg n$
- $n^3$ , som er $o(n^3\lg n)$
- $n^2\lg^2 n$ , som er $o(n^3)$ og dermed enda mindre

Det raskest voksende leddet er $n^3\lg n$ , og det er merket $\Theta$ . Ingen ledd
mangler øvre grense.

Svar: $\Theta(n^3\lg n)$ .

Merk hvorfor svaret ikke kan skrives $\Theta(n^3)$ : logaritmefaktoren er en ekte
vekstforskjell, ikke en konstant. $n^3\lg n$ delt på $n^3$ er $\lg n$ , som vokser
uten grense — altså er $n^3\lg n = \omega(n^3)$ .

📝Oppgave 13

Eksamensnivå, sjanger A

Forenkl hver brøk til ett strammeste uttrykk:

a) $\dfrac{\Theta(n^5)}{\Omega(n^2)}$

b) $\dfrac{\Omega(n^4\lg n)}{O(n^2)}$

c) $\dfrac{\Theta(n^6)}{\Theta(n^3)}$

📝Oppgave 14

Eksamensnivå, sjanger A…

Et sett gir deg tre deloppgaver.

a) La $f(n) = n^2/\lg n$ . Er $f(n) = \Theta(n^2)$ ? Er $f(n) = O(n^2)$ ? Er
$f(n) = \omega(n)$ ? Svar for hver.

b) Forenkl til ett strammeste uttrykk:
$\dfrac{\Theta(n^7)}{\Theta(n^3)} + O(n^4) + \Theta(n^3\lg^2 n)$

c) Forklar med én setning hvorfor svaret i b) ikke kunne vært skrevet
$\Theta(n^3\lg^2 n)$ .

Hele oppskriften i én oppgave: klassifisering med forholdstesten, brøk med
ekstremverdier, sum med dominerende ledd, og til slutt en begrunnelse på én
linje. Det er nøyaktig slik en sjanger A-oppgave med deloppgaver er bygd opp.

Klarer du denne på under fem minutter uten å slå opp, sitter kapitlet. Bruker du
lengre tid, er det som regel steg 1 i oppskriften som mangler: å skrive leddene
under hverandre med vekstklassen på hvert.

Begrepsbank

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

Symbolet

O

— øvre grense

g

Symbolet

\Omega

— nedre grense

g

Symbolet

\Theta

— tett grense

g

Symbolet

o

— strengt mindre

g

Symbolet

\omega

— strengt større

g

Strammeste grense

O(n^3)

Dominerende ledd i en sum

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

Når et ledd fjerner den øvre grensen

\Omega

Brøkregelen: ekstremverdi i teller og nevner

\Theta(g)

Forholdstesten

f(n)/g(n)

Sjanger A — asymptotisk forenkling

Oppgavetypen dette kapitlet drilles på: du får et sammensatt uttrykk og skal skrive det som ett strammeste uttrykk. Den er med i 100 % (17 av de 17 settene i grunnlaget), ofte med 2-3 oppgaver i samme sett. Svarformen er én linje — ett uttrykk, ingen utledning. Kravet som avgjør uttellingen, er at svaret er det strammeste, ikke bare et sant svar.

Sjanger D — definisjonsspørsmålet

c

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.