1.6 DRILL — Rekurrensløsning med navngitt metode

Full drill på sjanger B: velg riktig metode (masterteorem / iterasjon / substitusjon), løs, og oppgi svaret på riktig form (asymptotisk vs. eksakt).

80 min

13 oppgaver

DRILLRekurrensløsning med navngitt metode

Din fremgang i kapitlet

0 / 13 oppgaver

Kapitlets plass i kurset

Bygger på

1.5Rekurrenser — iterasjon, substitusjon og splitt-og-hersk

Brukes videre i

1.PPrøver til del 1: Asymptotisk analyse og rekurrenser

Rekurrenser er registrert i 13 av de 17 settene i grunnlaget (76 %).
Grunnlaget er de 17 settene fra august 2015 til august 2023 som er gjennomgått
tema for tema — det er nevneren hver gang boka oppgir en prosent.

Sjangeren er én, og den er smal nok til å drilles ferdig:

- Sjanger B — rekurrensløsning med navngitt metode, altså at du sier
hvilken metode du brukte og oppgir svaret på den formen oppgaven ber om.
Bruker du masterteoremet, skal tilfellet oppgis.

Høyeste prioritet — dette må sitte. To ting avgjør uttellingen: at metoden
er riktig valgt og navngitt, og at svarformen er den oppgaven ba om.

De tre feilene som koster mest, i rekkefølge:

1. Feil masterteorem-tilfelle, og særlig å glemme logaritmefaktoren i
tilfelle 2. Svaret der er $\lg^{k+1} n$ , ikke $\lg^{k} n$ .
2. Asymptotisk svar der oppgaven ba om et eksakt uttrykk. $\Theta(n^2)$ er
ikke et svar på «finn et eksakt uttrykk».
3. Å bruke masterteoremet på en rekurrens som faller utenfor. Det gir et
svar som ser riktig ut og er galt — mens det å påpeke at teoremet ikke
gjelder, gir uttelling.

Slik er kapitlet lagt opp (80 min):

Innhold	Tid
Løsningsoppskriften	ca. 10 min
Den gjennomarbeidede eksamenscasen	ca. 14 min
Drill på masterteoremet, alle tre tilfellene	ca. 22 min
Drill på iterasjon og eksakte svar	ca. 16 min
Drill på substitusjon	ca. 10 min
Blandet: hvilken metode?	ca. 8 min

— naturlig pausepunkt — etter masterteorem-drillen. Resten kan tas i en egen
økt.

Forkunnskaper

- kap. 1.4 — masterteoremet, de tre tilfellene og
regularitetsbetingelsen.
- kap. 1.5 — iterasjonsmetoden, substitusjonsmetoden og
splitt og hersk.
- kap. 1.1 — de asymptotiske symbolene.

Er induksjon ustøtt, er Induksjonsbevis den grundige
gjennomgangen og Induksjon den mykere. Summeformlene finner du i
Rekker og summasjon og
Geometriske følger og rekker.

Dette kapitlet legger ikke til nytt stoff. Det gjør stoffet til en ferdighet du
kan utføre på fem minutter under tidspress.

Notasjons- og pseudokodeliste

📜Løsningsoppskriften for en rekurrensoppgave

Steg 1 — les hva oppgaven ber om. Står ordet «eksakt» eller «lukket
uttrykk» der? Da er det iterasjon, uansett hvilken form rekurrensen har. Står
det «vis at

T(n) = O(\dots)

»? Da er det substitusjon.

Steg 2 — er rekurrensen på formen $aT(n/b) + f(n)$ med $a \ge 1$ og
$b > 1$ ? Er den det, og oppgaven vil ha en asymptotisk grense, bruk
masterteoremet. Er den ikke det — for eksempel $T(n) = T(n-1) + f(n)$ — bruk
iterasjon.

Steg 3 ved masterteoremet — regn ut $n^{\log_b a}$ først. Ikke gjett.
$\log_2 8 = 3$ , $\log_3 9 = 2$ , $\log_4 2 = 1/2$ , $\log_2 7 \approx 2{,}807$ .

Steg 4 — sammenlign $f(n)$ med $n^{\log_b a}$ , og velg tilfelle:

Forholdet	Tilfelle	Svar
$f(n)$ vokser en hel potens langsommere	1	$\Theta(n^{\log_b a})$
$f(n) = \Theta(n^{\log_b a}\lg^{k} n)$ , $k \ge 0$	2	$\Theta(n^{\log_b a}\lg^{k+1} n)$
$f(n)$ vokser en hel potens raskere, og regularitet holder	3	$\Theta(f(n))$

Steg 5 — sjekk at tilfellet faktisk gjelder. I tilfelle 1 og 3 må gapet
være en hel potens av

n

, ikke bare en logaritme;

\varepsilon

må være
strengt positiv. I tilfelle 3 skal regularitetsbetingelsen

af(n/b) \le c\,f(n)

skrives ut på én linje.

Steg 6 — er $k$ negativ, faller rekurrensen utenfor pensumvarianten. Si
det. $T(n) = 2T(n/2) + n/\lg n$ er det klassiske eksemplet.
Steg 7 ved iterasjon: skriv ut tre innsettinger, finn det generelle leddet,
finn hvilken $i$ som treffer grunntilfellet, summer. Grunntilfellets verdi skal

med i det eksakte uttrykket.
Steg 8 ved substitusjon: sett hypotesen inn der $T$ -uttrykket står, regn

ut, og vis at du ender på nøyaktig den formen du antok. Er det et restledd
igjen, er gjetningen for optimistisk.
Steg 9 — skriv svaret. Metodens navn, tilfellet hvis masterteoremet, og

selve uttrykket. To til tre linjer.

✏️Eksempel 1: Gjennomarbeidet eksamenscase med margnotater

Tre deloppgaver av den typen som kommer sammen på arket. Les margnotatene: de
sier hva som gir uttelling ved hvert steg.

a) Løs $T(n) = 2T(n/2) + n\lg n$ og oppgi tilfellet.

b) Finn et eksakt uttrykk for $T(n) = T(n-1) + n$ med $T(0) = 0$ .

c) Løs $T(n) = 3T(n/4) + n\lg n$ og oppgi tilfellet.

a) Metode: masterteoremet.

$a = 2$ , $b = 2$ , altså $n^{\log_2 2} = n$ .

$f(n) = n\lg n = \Theta(n^{1}\lg^{1} n)$ , altså $\Theta(n^{\log_b a}\lg^{k} n)$
med $k = 1$ . Det er tilfelle 2.

$T(n) = \Theta(n\lg^{2} n)$

Margnotat. Her faller de fleste poengene. Svaret er $\lg^{k+1} n$ , altså
$\lg^2 n$ — du legger til én logaritme, du beholder ikke den du hadde. Skriver
du $\Theta(n\lg n)$ , har du gitt Merge-Sorts svar på en rekurrens som er
dyrere.

Margnotat. Tilfellet skal oppgis. «Tilfelle 2» er to ord og gir uttelling.

b) Metode: iterasjon.

$T(n) = T(n-1) + n = T(n-2) + (n-1) + n = \dots = T(0) + 1 + 2 + \dots + n$

$T(n) = \frac{n(n+1)}{2}$

Margnotat. Oppgaven ba om et eksakt uttrykk. Svarer du $\Theta(n^2)$ , er
påstanden sann og svaret galt — det er ikke den formen som ble etterspurt.

Margnotat. Grunntilfellet $T(0) = 0$ bidrar ingenting her, men det skal med i
regnestykket. Hadde det vært $T(0) = 4$ , ville svaret vært $n(n+1)/2 + 4$ .

c) Metode: masterteoremet.

$a = 3$ , $b = 4$ , altså $n^{\log_4 3} \approx n^{0{,}79}$ .

$f(n) = n\lg n$ vokser strengt raskere enn $n^{0{,}79}$ — og gapet er en hel
potens: $n\lg n = \Omega(n^{0{,}79+\varepsilon})$ holder for eksempel med
$\varepsilon = 0{,}2$ . Vi er i tilfelle 3.

Regularitetsbetingelsen: $\displaystyle 3f(n/4) = 3\cdot\frac{n}{4}\lg\frac{n}{4} \le \frac{3}{4}\,n\lg n = c\,f(n)$ med $c = 3/4 < 1$ . Den holder. (Kontrollert
numerisk for $n$ opp til 65 536.)

$T(n) = \Theta(n\lg n)$

Margnotat. I tilfelle 3 er svaret $\Theta(f(n))$ — ingen ekstra
logaritmefaktor. Å legge til én er en refleks fra tilfelle 2 og er galt her.

Margnotat. Regularitetsbetingelsen er ett av leddene som gir uttelling i
tilfelle 3. Én linje holder.

På eksamen leverer du de tre svarene under — resten er utregning:

- a) Masterteoremet, tilfelle 2: $\Theta(n\lg^2 n)$
- b) Iterasjon: $T(n) = n(n+1)/2$
- c) Masterteoremet, tilfelle 3 (regularitet oppfylt): $\Theta(n\lg n)$

Drill på masterteoremet (~22 min)

Seks oppgaver som roterer alle tre tilfellene, pluss den ene som faller
utenfor.

📝Oppgave 1

Eksamensnivå, sjanger B

Løs $T(n) = 8T(n/2) + n^3$ . Oppgi tilfellet.

📝Oppgave 2

Eksamensnivå, sjanger B

Løs $T(n) = 9T(n/3) + n$ . Oppgi tilfellet.

📝Oppgave 3

Eksamensnivå, sjanger B

Løs $T(n) = 4T(n/2) + n^2$ . Oppgi tilfellet.

📝Oppgave 4

Eksamensnivå, sjanger B

Løs $T(n) = 2T(n/4) + 1$ . Oppgi tilfellet.

📝Oppgave 5

Eksamensnivå, sjanger B

Løs $T(n) = 7T(n/2) + n^2$ . Oppgi tilfellet, og forklar med én setning hvorfor
svaret ikke er $\Theta(n^2\lg n)$ .

📝Oppgave 6

Eksamensnivå, sjanger B

Betrakt $T(n) = 2T(n/2) + \dfrac{n}{\lg n}$ .

a) Regn ut $n^{\log_b a}$ og sammenlign med $f(n)$ .
b) Kan pensumvarianten av masterteoremet brukes? Begrunn.

Drill på iterasjon og eksakte svar (~16 min)

Fire oppgaver. Alle ber om et eksakt uttrykk — les svarformen nøye.

📝Oppgave 7

Eksamensnivå, sjanger B

Finn et eksakt uttrykk for $T(n) = T(n-1) + 2^{n-1}$ med $T(0) = 0$ , og
navngi metoden.

📝Oppgave 8

Eksamensnivå, sjanger B

Finn et eksakt uttrykk for $T(n) = 3T(n-1)$ med $T(0) = 2$ , og navngi
metoden.

📝Oppgave 9

Eksamensnivå, sjanger B

En rutine kaller seg selv på en input som er to elementer kortere, og gjør $n$
enheter arbeid per kall: $T(n) = T(n-2) + n$ for like $n$ , med $T(0) = 0$ .

Finn et eksakt uttrykk for like $n$ .

📝Oppgave 10

Eksamensnivå, sjanger B

Betrakt $T(n) = T(n-1) + n$ med $T(0) = 0$ .

a) Oppgi et eksakt uttrykk.
b) Oppgi den strammeste asymptotiske grensen.
c) Forklar med én setning hvorfor de to svarene ikke er utskiftbare på
eksamen.

Drill på substitusjon (~10 min)

To oppgaver. Husk at uttellingen ligger i induksjonssteget, ikke i
gjetningen.

📝Oppgave 11

Eksamensnivå, sjanger B

Vis ved substitusjon at $T(n) = 2T(n/2) + n$ gir $T(n) = O(n\lg n)$ . Før
induksjonssteget ferdig.

📝Oppgave 12

Eksamensnivå, sjanger B

En kandidat vil vise at $T(n) = 4T(n/2) + n$ gir $T(n) = O(n^2)$ , og skriver:

«Anta $T(n/2) \le c(n/2)^2$ . Da er $T(n) \le 4c(n/2)^2 + n = cn^2 + n$ , som er
$O(n^2)$ .»

Er beviset gyldig? Svar ja eller nei, og forklar hvor det svikter — og hvordan
det kan repareres.

Blandet: hvilken metode? (~8 min)

Den siste oppgaven blander alt. På eksamen er dette den vanligste
innpakningen: tre rekurrenser på rad, ulike metoder.

📝Oppgave 13

Eksamensnivå, sjanger B

For hver rekurrens: navngi metoden, løs, og oppgi svaret på riktig form.

a) $T(n) = 2T(n/2) + n\lg n$
b) $T(n) = T(n-1) + n$ , $T(0) = 0$ — eksakt svar
c) $T(n) = 8T(n/2) + n^3$ — oppgi tilfellet
d) $T(n) = T(n/2) + \Theta(1)$

Typiske feil

Den første er den dyreste, og den kommer igjen og igjen.

- Å glemme logaritmefaktoren i tilfelle 2. Svaret er
$\Theta(n^{\log_b a}\lg^{k+1} n)$ — én logaritme mer enn $f(n)$ hadde.
For $T(n) = 8T(n/2)+n^3$ er svaret $\Theta(n^3\lg n)$ , ikke $\Theta(n^3)$ .
Dette er felle #5 — feil masterteorem-tilfelle.
- Å bruke tilfelle 2 med negativ $k$ . Pensumvarianten krever $k \ge 0$ .
$T(n) = 2T(n/2) + n/\lg n$ har $k = -1$ og faller utenfor — si det, ikke
regn videre.
- Å legge til en logaritme i tilfelle 3. Der er svaret $\Theta(f(n))$ ,
punktum. Logaritmen hører til tilfelle 2.
- Å hoppe over regularitetsbetingelsen i tilfelle 3. Den er ett av leddene
som gir uttelling, og den skrives på én linje.
- Å oppgi asymptotisk grense der oppgaven ber om et eksakt uttrykk, eller
motsatt. Ordet «eksakt» styrer svarformen.
- Å glemme grunntilfellet i et eksakt svar. Med $T(0) = 2$ i stedet for
$T(0) = 0$ blir svaret et annet.
- Å ikke navngi metoden. Sjangeren heter «rekurrensløsning med navngitt
metode», og navnet er ett ord.
- Å ende induksjonssteget på feil form. Kommer du ut med $cn^2 + n$ når du
antok $cn^2$ , har du ikke vist påstanden — konstanten har vokst.

Og den gjennomgående: å tvinge masterteoremet på en rekurrens som ikke er på
formen $aT(n/b) + f(n)$ . Å påpeke at teoremet ikke gjelder, gir uttelling.

Rekurrensene du bør kjenne igjen på ett blikk

Rekurrens	Metode	Svar
$T(n) = T(n/2) + \Theta(1)$	masterteoremet, tilfelle 2 ( $k=0$ )	$\Theta(\lg n)$
$T(n) = 2T(n/2) + \Theta(n)$	masterteoremet, tilfelle 2 ( $k=0$ )	$\Theta(n\lg n)$
$T(n) = 2T(n/2) + n\lg n$	masterteoremet, tilfelle 2 ( $k=1$ )	$\Theta(n\lg^2 n)$
$T(n) = 2T(n/2) + n^2$	masterteoremet, tilfelle 3	$\Theta(n^2)$
$T(n) = 4T(n/2) + n$	masterteoremet, tilfelle 1	$\Theta(n^2)$
$T(n) = 8T(n/2) + n^3$	masterteoremet, tilfelle 2 ( $k=0$ )	$\Theta(n^3\lg n)$
$T(n) = 7T(n/2) + n^2$	masterteoremet, tilfelle 1	$\Theta(n^{\lg 7})$
$T(n) = 2T(n/4) + 1$	masterteoremet, tilfelle 1	$\Theta(\sqrt{n})$
$T(n) = T(n-1) + \Theta(1)$	iterasjon	$\Theta(n)$
$T(n) = T(n-1) + n$	iterasjon	eksakt $n(n+1)/2$ ; $\Theta(n^2)$
$T(n) = T(n-1) + 2^{n-1}$	iterasjon	eksakt $2^n - 1$ ; $\Theta(2^n)$
$T(n) = 2T(n-1) + 1$	iterasjon	eksakt $2^n - 1$ ; $\Theta(2^n)$
$T(n) = 2T(n/2) + n/\lg n$	ingen — $k = -1$	faller utenfor pensumvarianten

De fem øverste dekker de fleste algoritmene i denne boka. Kjenner du dem igjen
uten å regne, sparer du minutter du trenger andre steder.

Begrepsbank

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

Sjanger B — rekurrensløsning med navngitt metode

oppgavetypen der du får en rekurrens og skal løse den. Svarformen er metodens navn, svaret på riktig form — asymptotisk eller eksakt — og for masterteoremet også hvilket tilfelle som gjelder. Metodenavnet er ett ord, og det er en del av det som gir uttelling.

Sjekklista for metodevalg

aT(n/b)+f(n)

Tilfelle 2 og logaritmefaktoren

f(n) = \Theta(n^{\log_b a}\lg^{k} n)

Betingelsen

k \ge 0

k = 0

Regularitetsbetingelsen

af(n/b) \le c\,f(n)

Tilfelle 3 og fraværet av logaritme

\Theta(f(n))

Iterasjon og grunntilfellet

T(n) = T(n-1)+3

Substitusjonssteget

T

Felle #5 — feil masterteorem-tilfelle

\lg n

Eksakt mot asymptotisk svarform

T(n)

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.