1.2 Forenkling av asymptotiske uttrykk

Det leddet i en sum som vokser raskest, og som alene bestemmer summens
asymptotiske klasse.

Du finner det ved å plassere leddene i vekstordningen
$1 < \lg n < n < n\lg n < n^2 < n^3 < 2^n < n!$ og velge det som ligger lengst
til høyre. I $5n^2 + 100n + 3000$ er det $5n^2$, og summen er $\Theta(n^2)$.
Konstantfaktoren 5 forsvinner sammen med resten.

Det uttrykket som gir mest informasjon blant alle sanne påstander om samme
funksjon: $\Theta$ foran $O$ og $\Omega$, og $O(n^2)$ foran $O(n^3)$.

Løsningsforslagene forventer det strammeste. Å svare $O(n^3)$ når $\Theta(n^2)$
kan vises, er felle #4 — å oppgi en løs asymptotisk grense der en strammere
finnes. Påstanden er sann, men den kaster bort informasjon, og et slikt svar
regnes ikke som fullstendig.

Svarformen du bruker når ett uttrykk ikke kan fange både gulv og tak: du oppgir
den strammeste $\Omega$-påstanden og den strammeste $O$-påstanden ved siden av
hverandre.

For $n + \Theta(n^2) + O(n^3)$ er svaret «$\Omega(n^2)$ og $O(n^3)$». Dette er et
fullstendig svar og gir full uttelling. Å presse fram ett $\Theta$-uttrykk der
det ikke finnes ett, er derimot direkte galt.

Den største eller minste veksten et asymptotisk ledd kan ha, avhengig av hvilken
retning du leter etter en grense i.

Et $O(g)$-ledd har $g$ som største mulige vekst og ingen minste — det kan være så
lite som en konstant. Et $\Omega(g)$-ledd har $g$ som minste mulige vekst og
ingen største. Et $\Theta(g)$-ledd er låst til $g$ begge veier. Å bytte hvert ledd
med riktig ekstremverdi er selve arbeidsmetoden i forenklingsoppgaver.

Regelen som sier at en sum med et $\Omega$- eller $\omega$-ledd ikke har noen
øvre grense i det hele tatt.

Begrunnelsen er at $\Omega(g)$ bare setter et gulv: leddet kan være $g$, men det
kan like gjerne være $2^n$. Derfor er $\Omega(n^2) + O(n^3)$ verken $O(n^3)$
eller $\Theta$ av noe — det strammeste sanne svaret er $\Omega(n^2)$. Å svare
$O(n^3)$ her er en av de vanligste feilene i sjangeren.

Når $\Omega$ står utenpå en hel sum, spør du hva det minste innmaten kan
være — for det er alt $\Omega$ lover.

I $\Omega(n + \Theta(n^2) + O(n^3))$ er det minste innmaten kan bli, i
størrelsesorden $n^2$, siden $O(n^3)$-leddet kan skrumpe til en konstant. Svaret
er derfor $\Omega(n^2)$, ikke $\Omega(n^3)$. Tilsvarende ville $O$ utenpå spurt
etter det største innmaten kan være.

En brøk av asymptotiske uttrykk behandles ved å sette teller og nevner til hver
sin ekstremverdi, og deretter forkorte.

Retningen bestemmer hvilken ekstremverdi du velger: størst teller og minst
nevner gir den øvre grensen, minst teller og størst nevner gir den nedre.
Å behandle brøken som ett samlet ledd er den vanligste feilen i denne varianten —
$\Theta(n^4)/\Omega(n^2)$ er $O(n^2)$, ikke $\Theta(n^2)$.

Når det finnes et tak, men ikke noe gulv. Det skjer så snart et ledd kan skrumpe
fritt: et $\Omega$ i nevneren, eller et $O$-ledd som får være vilkårlig lite.

$\Theta(n^4)/\Omega(n^2)$ er et rent eksempel. Nevneren er minst $n^2$, og det
gir taket $n^2$ — men nevneren kan også være $n^4$, og da er kvotienten en
konstant. Ingen $\Omega$-påstand overlever, så $O(n^2)$ er hele svaret.

I en sum av asymptotiske ledd overlever bare det raskest voksende:
$\Theta(f) + \Theta(g) = \Theta(\max(f, g))$.

Begrunnelsen ligger i definisjonen: to funksjoner som begge er høyst
$c\,\max(f,g)$, har en sum som er høyst $2c\,\max(f,g)$, og faktoren 2
forsvinner inn i konstanten. Samme regel gjelder for $O$ med $O$ og for $\Omega$
med $\Omega$.

Et $o(g)$-ledd vokser strengt saktere enn $g$ og kan aldri være det dominerende
leddet i en sum der noe av størrelsesorden $g$ eller større står.

Praktisk: i $\Theta(n^2) + o(n^2)$ er svaret $\Theta(n^2)$. Leddet forsvinner.
Men et $o(n^3)$-ledd er ikke like harmløst i en sum av $n^2$-ledd — det kan være
$n^{2{,}5}$, altså større enn $n^2$, uten å bryte med $o(n^3)$.

Derfor kan en sum av bare $O$-ledd aldri gi et $\Theta$-svar: hvert ledd kan være
så lite som en konstant, så hele summen kan være $\Theta(1)$.

Enhver konstant foran et asymptotisk uttrykk forsvinner. Både
$7\,\Theta(n\lg n)$ og $\Theta(n\lg n)$ beskriver det samme, og $5n^2$ er
$\Theta(n^2)$.

Konstanten absorberes i $c_1$ og $c_2$ fra definisjonen av $\Theta$. Det samme
gjelder grunntallet i en logaritme, siden $\log_b n = \lg n / \lg b$.

Et produkt behandles ledd for ledd på samme måte som en brøk:
$\Theta(f) \cdot \Theta(g) = \Theta(f \cdot g)$.

Med løsere symboler arver produktet løsheten: $O(f) \cdot O(g) = O(f \cdot g)$,
men $\Omega(f) \cdot O(g)$ har verken tak eller garantert gulv i noen enkelt
klasse. Ganger du inn en konstant, endres ingenting.

Rekkefølgen $1 < \lg n < n < n\lg n < n^2 < n^3 < 2^n < n!$ er verktøyet du
bruker til å plukke ut det dominerende leddet.

I en forenklingsoppgave er første grep alltid å plassere hvert ledd i denne
kjeden. Leddet lengst til høyre vinner; alle de andre drukner. De sammensatte
uttrykkene passer også inn: $n^2\lg n$ ligger mellom $n^2$ og $n^3$.

Å svare med en løsere grense enn den du kan forsvare. Dette er felle #4, og den
er den vanligste enkeltfeilen i sjanger A.

Konkret: å svare $O(n^2)$ når $\Theta(n^2)$ kan vises, eller $O(n^3)$ når
$O(n^2)$ holder. Påstandene er sanne, men de gir bort informasjon oppgaven
etterspør. Sjekk alltid til slutt: har jeg gulv i tillegg til tak, og er taket så
lavt som det kan bli?

Et ledd kan bare bestemme svaret hvis det har det raskest voksende gulvet eller
det høyeste taket, avhengig av retningen du ser etter.

Et $O$-ledd bidrar aldri til gulvet, fordi det kan være en konstant. Et
$o$-ledd bidrar heller aldri. Til gjengjeld bidrar et $\Omega$- eller
$\omega$-ledd aldri til taket — det finnes ikke noe tak å bidra med.

Fem steg, i denne rekkefølgen: identifisér leddene; løs opp eventuelle brøker
ledd for ledd; behold det raskest voksende leddet i en sum; sjekk om noe ledd
mangler tak; skriv det strammeste enkeltuttrykket.

Steg fire er det som oftest hoppes over. Et $\Omega$- eller $\omega$-ledd et sted
i uttrykket betyr at ingen $O$-påstand kan gjelde, og da er svaret en ren nedre
grense.

To $\Theta$-ledd gir alltid et $\Theta$-svar, fordi begge har både gulv og tak:
$\Theta(n^2) + \Theta(n\lg n) = \Theta(n^2)$.

Dette er den eneste sumformen som garantert gir en tett grense. Så snart ett av
leddene er $O$, $\Omega$, $o$ eller $\omega$, må du sjekke gulv og tak hver for
seg før du velger symbol.

Eksamensoppgavene i sjanger A gjenbruker et lite knippe former: ren sum av
konkrete ledd; sum med blandede symboler; $\Omega$ eller $O$ utenpå en sum; alle
fem symbolene i samme sum; enkel brøk med ett løst ledd; enkel brøk med to låste
ledd; og sum av to brøker.

Eksponentene varierer fra sett til sett, men formene gjør det ikke. Gjenkjenner
du formen, har du svaret på under et minutt.

Ett strammeste uttrykk på én linje — eller to uttrykk når nedre og øvre grense
ligger i ulike klasser.

Løsningsforslagene svarer med selve uttrykket og ikke stort mer. Utregningen din
hører hjemme på kladden. Oppgaven ber om et uttrykk, ikke om en forklaring av
hvordan du kom fram til det, med mindre den ber om begrunnelse eksplisitt.

For $n + \Theta(n^2) + O(n^3)$ gir det $O$-svaret $O(n^3)$ og $\Omega$-svaret
$\Omega(n^2)$. Samme innmat, to helt ulike tall, fordi de to symbolene leter i
hver sin retning.

Et fullt gyldig svar. Uttrykk med et $\Omega$- eller $\omega$-ledd har ofte ingen
øvre grense i det hele tatt, og da er en ren $\Omega$- eller $\omega$-påstand det
strammeste som finnes.

Eksempler: $\Omega(n^2) + O(n^3) = \Omega(n^2)$, og
$\Omega(n^3)/O(n^2) = \Omega(n)$. Å legge til «og $O$ av noe» ville vært å påstå
mer enn uttrykket gir dekning for.