La oss anta det foreligger en algoritme for et spesielt problem der n (positivt heltall) er et mål for størrelsen på problemet. Tidsforbruket t(n) til algoritmen er derfor avhengig av n. t(n) er av orden høyst f(n) hvis det fins positive konstanter C og N slik at t(n) ≤ Cf(n) for alle n ≥ N. I stor O-notasjon er skrivemåten t(n) = O(f(n)). f(n) kalles ofte for vekstfunksjonen. Det betyr at når n ≥ N vil grafen til t(n) ligge under grafen til Cf(n).
Følgende kan vises:
O(k(f(n)) = O(f(n)), her er k er en positiv konstant
O(f(n)) + O(g(n)) = O(f(n) + g(n))
O(f(n))O(g(n)) = O(f(n)g(n))
Vi har også at O(k) = O(1), for eksempel O(10000) = O(1)
Følgende nyttige identiteter gjelder:
1 + 2 + 3 + . . . + n-1 + n = n(n + 1)/2 og dermed har vi også
1 + 2 + 3 + . . . + n-2 + n-1 = (n-1)n/2
Eks: Gitt en algoritme som bruker 3n2 + 9n operasjoner, dvs t(n) = 3n2 + 9n.
La oss vise at t(n) = O(n2) ut fra definisjonen over.
Siden 9n ≤ n2 for alle n ≥ 9 har vi at 3n2 + 9n ≤ 4n2 for alle n ≥ 9.
Vi lar f(n) = n2, C = 4 og N = 9. Se definisjon over som er uthevet.
Altså har vi at t(n) = 3n2 + 9n = O(n2).
Kommentar: Vi ser at det er det dominerende leddet (det leddet som vokser raskest når n øker), her n2, som vi angir med O-notasjonen. Det betyr at i oppgaver der vi bare skal angi tidsforbruket til en algoritme uttrykt i O-notasjon behøver vi ikke finne C og N. Men noen ganger der vi skal måle tidsforbruket mer nøyaktig må vi ta hensyn til konstanten i det dominerende leddet + eventuelt de lavere ordens leddene.
Vi må også kjenne til følgende når vi senere skal sammenligne
tidsforbruket til ulike algoritmer:
O(1) < O(logn) < O(n) < O(nlogn) < O(n2 ) < O(n3) < O(2n) < O(n!) < O(nn)
Oppgaven:
Hva er størrelsesorden uttrykt i O-notasjon for algoritmen når tidsfunksjonen er gitt som:
(dvs. vi behøver ikke finne C og N)
i) 4n^2 + 50n – 10
ii) 10n + 4 log2n + 30
iii) 13n^3 – 22n^2 + 50 n + 20
iv) 35 + 13 log2n
Det ser kanskje veldig lett ut for mange, men det er er litt stress for meg...
Setter pris på god hjelp 
