Formelsamling

Til eksamen i dette emnet deles det ikke ut noen formelsamling. Oversikten under er en studieressurs: på eksamen må alt kunnes uten hjelpemidler.

01 Asymptotisk notasjon

$\displaystyle O(n^a) + \Omega(n^b) + \Theta(n^c) = \Omega(n^b + n^c)$ Summer øvre og nedre grenser hver for seg. Står vi igjen med bare en nedre grense, skrives den med $\Omega$ .

02 Insertion-Sort

$\displaystyle \sum_{k=1}^{n-1} k = \dfrac{n(n-1)}{2} = \Theta(n^2)$ Trekanttall, og antall forskyvninger i verste tilfelle for Insertion-Sort