Aritmetiske uttrykk med asymptotisk notasjon kan være enkle, når alle leddene bruker samme operator, som f.eks.: $O(n) + O(n^2) = O(n + n^2) = O(n^2)$ Men hva skjer når man blander forskjellige operatorer?

Inneholder forklaringer på denne typen oppgaver for eksamen november 2019, august 2021, desember 2021, august 2022, og desember 2022.

For eksempel:

\[\Omega(n) + O(n^2)\]

Hvordan kan vi forenkle dette? Først og fremst må vi huske at hvert ledd, som f.eks. $O(n^2)$, representerer en ukjent funksjon, som f.eks. $2n+9$ eller $3n^2 + n$. En fremgangsmåte kan da være:

  1. For hvert ledd, spør deg selv: Hvor lite kan det være? Hvor stort?

  2. Hvis alle ledd er så små som mulig, hvor lite blir resultatet?

  3. Hvis alle ledd er så store som mulig, hvor stort blir resultatet?

En måte å tydeliggjøre dette på er å sette det opp som en tabell, med ett ledd per rad, én kolonne for minimum og én for maksimum (punkt 1). Vi kan så summere hver kolonne for seg (punkt 2 og 3).

Ledd Hvor lite? Hvor stort?
$\Omega(n)$ $n$ $\infty$
$O(n^2)$ $0$ $n^2$
Sum $n$ $\infty$

Vi ser da at den minste verdien uttrykket kan ha, asymptotisk sett, er $n$, mens det er ingen øvre grense. Dermed kan vi konkludere:

\[\Omega(n) + O(n^2) = \Omega(n)\]

Uttrykkene jeg bruker når jeg beskriver hvor store eller små leddene kan bli må tolkes asymptotisk. Jeg kunne like gjerne ha skrevet $\Theta(n)$, etc., men det kan være enklere å ikke blande inn mer notasjon enn nødvendig. På samme måte, er bruken av $0$ og $\infty$ forenklinger, som bare betyr at vi ikke har noen nedre eller øvre grense.

I november 2019 ble vi i oppgave 10 bedt om å forenkle følgende:

\[O(n) + \Omega(n) + \Theta(n) + o(n) + \omega(n)\]

Det kan vi gjøre på samme måte:

Ledd Hvor lite? Hvor stort?
$O(n)$ $0$ $n$
$\Omega(n)$ $n$ $\infty$
$\Theta(n)$ $n$ $n$
$o(n)$ $0$ $n-\epsilon$
$\omega(n)$ $n+\epsilon$ $\infty$
Sum $n+\epsilon$ $\infty$

Her er $n-\epsilon$ og $n+\epsilon$ bare intuitive påminnelser om at her må funksjonen være asymptotisk strengt mindre eller strengt større enn $n$ (som er det $o(n)$ og $\omega(n)$ betyr).

Her har ser vi at den nedre grensen er strengt større enn $n$, og vi har ingen øvre grense. Dermed kan vi konkludere:

\[O(n) + \Omega(n) + \Theta(n) + o(n) + \omega(n) = \omega(n)\]

I august 2022 er oppgave 6 å forenkle følgende, der $a$, $b$ og $c$ er positive heltallskonstanter:

\[O(n^a) + \Omega(n^b) + \Theta(n^c)\]

Vi kan bruke samme fremgangsmåte:

Ledd Hvor lite? Hvor stort?
$O(n^a)$ $0$ $n^a$
$\Omega(n^b)$ $n^b$ $\infty$
$\Theta(n^c)$ $n^c$ $n^c$
Sum $n^b + n^c$ $\infty$

Merk at vi her ikke kan forenkle $n^b + n^c$ mer, fordi vi ikke vet hvilken av $b$ og $c$ som er størst. Vi får altså:

\[O(n^a) + \Omega(n^b) + \Theta(n^c) = \Omega(n^b + n^c)\]

I desember 2022, oppgave 6, har vi følgende uttrykk:

\[\Omega(n+\Theta(n^2) + O(n^3))\]

Det er ikke bare en sum av flere ledd, men vi kan gjøre utregningen på det innerste uttrykket først:

Ledd Hvor lite? Hvor stort?
$n$ $n$ $n$
$\Theta(n^2)$ $n^2$ $n^2$
$O(n^3)$ $0$ $n^3$
Sum $n^2$ $n^3$

Her kan altså den innerste summen bli alt fra $n^2$ til $n^3$ (asymptotisk), som igjen betyr at hele uttryket kan bli alt fra $\Omega(n^2)$ til $\Omega(n^3)$. Det minste det kan bli er da $n^2$, mens det er ingen grense for hvor stort det kan bli. Altså kan vi konkludere:

\[\Omega(n + \Theta(n^2) + O(n^3)) = \Omega(n^2)\]

Det å sette opp en tabell kan bli mindre nyttig om det er mer multiplikasjon og divisjon, for eksempel, men vi kan likevel følge den samme tankegangen. Hvor lite eller stort kan hvert asymptotiske deluttrykk bli, og hva blir hele uttrykket da? Hvordan kan vi så beskrive det med asymptotisk notasjon?

For eksempel oppgave 6 fra desember 2021:1

\[\frac{\Omega(n^3)}{O(n^2)} + \frac{\Theta(n^5)}{\Theta(n^3)} + \frac{O(n^7)}{\Omega(n^4)}\]

Om vi ser på hva de minste og største verdiene kan være, så ser vi straks at $O(n^2)$, under den første brøkstreken, kan bli vilkårlig lite, som igjen gjør at $\Omega(n^3)/O(n^2)$ kan bli vilkårlig stort. Med andre ord vet vi allerede nå at hele uttrykket kan bli vilkårlig stort.

Hvor lite kan det bli? Da må tellerne bli så små som mulige, mens nevnerne må bli så store som mulige, asymptotisk sett. Intuitivt kan vi tenke på det slik:

\[\frac{n^3}{n^2} + \frac{n^5}{n^3} + \frac{0}{n^4} = n + n^2 + 0\]

Det vil si, det minste vi kan få, asymptotisk sett, er $n^2$, så svaret blir:

\[\frac{\Omega(n^3)}{O(n^2)} + \frac{\Theta(n^5)}{\Theta(n^3)} + \frac{O(n^7)}{\Omega(n^4)} = \Omega(n^2)\]

På tilsvarende måte kan vi se at i uttrykket

\[\Omega(n^2)\cdot O(\lg n) + \Theta(n)\]

fra oppgave 8, august 2021, kan $\Omega(n^2)\cdot O(\lg n)$ bli både vilkårlig stort (pga. $\Omega(n^2)$) og vilkårlig lite (pga. $O(\lg n)$), mens hele uttrykket ikke kan bli asymptotisk mindre enn $n$ (pga. $\Theta(n)$-leddet). Dermed får vi:

\[\Omega(n^2)\cdot O(\lg n) + \Theta(n) = \Omega(n)\]

Det viktigste å spørre seg om når du står overfor et slikt uttrykk er altså:

Hvor store og små kan de ulike delene bli? Hvor stort eller smått blir hele uttrykket da?



  1. Vi får beskjed om å anta at uttrykket er veldefinert, så funksjonene under brøkstrekene kan ikke bli $0$. ↩