Eksempel 1:
1. sum = 0
2. x = 100
3. for i = 1 to n:
4.     for j = 1 to x:
5.        sum += i*j



3: O(n)
4: O(100)
-> O(100n) = O(n)


Eksempel 2:
1. for i = 1 to n:
2.     for j = i to n:
3.         for k = i to j:
4.             print(i, j, k)



1: O(n)
2: O(n)
3: O(n)
-> O(n^3)


Eksempel 3:
1. x = 0
2. for i = 0 to n:
3.     for j = 0 to i^2:
4.         x = x + j



2: O(n)
3: O(n^2) fordi i=n, i^2=n^2
-> O(n^3)


Eksempel 4:
1. x = 0
2. for i = 1 to n:
3.     for j = n down to i, step j = j/2:
4.         x = x + i + j



2: O(n)
3: O(log n)
-> O(n log n)


Eksempel 5:
1. x = 0
2. for i = n down to 1, step i = i/2:
3.     for j = 1 to i:
4.         x = x + i + j



3: n + n/2 + n/4 + n/8 ... = 2n
-> O(n)


Eksempel 6:
1. s = 0
2. for i = 1 to n+1:
3.     for j = 1 to i+1:
4.         for k = i to j+1:
5.             s = s + k



2: O(n)
3: O(n)
4: Kj?rer 0 eller 1 gang avhengig av om j < i eller j = i
-> O(n^2)


Eksempel 7:
1. func rec(n):
2.     if n > 1:
3.         return 3 * rec(n/3)
4.     else:
5.         return 0



3: Deler n p? 3 for hver rekursive runde
-> O(log3 n) = O(log n)


Eksempel 8:
1. func rec2(n, m, o):
2.     if n <= 0:
3.         print(n, m, o)
4.     else:
5.         rec2(n-1, m+1, o)
6.         rec2(n-1, m, o+1)



5+6: 2 rekursive kall der n telles ned med 1
1 rekursivt kall ville f?rt til O(n)
2 -> O(2^n)


Eksempel 9: Eksamen 2020 subanagram
2: O(W) +
3: O(S) *
(4: O(W) + 5: O(W)) +
6: O(1)
-> O(W) + O(S * 2W) + O(1) = O(S * W)


Eksempel 10: Eksamen 2020 s?k
n = |A|
k = |B|
Print tallene som er i b?de A og B.
3 gir alltid rett svar, en kan gi feil svar.
N?r skal man bruke de forskjellige?

2: Bin?rs?k p? input som kan v?re usortert -> kan gi feil svar
4: Sorterer for hver iterasjon -> un?dvendig og vil aldri gi best kj?retid

S?k: O(n)
Bin?rs?k: O(log n)
Heapsort: O(n log n)

## k = 1
1: O(n)
3: O(n log n) + O(log n) -> O(n log n)
1 er best

## k = log n:
1: O(n log n)
3: O(n log n) + O(log n * log n) = O(n log n)
1 og 3 er like gode

## k = n:
1: O(n^2)
3: O(n log n) + O(n log n) = O(n log n)
3 er best

## k = n^2:
1: O(n^3)
3: O(n log n) + O(n^2 log n) = O(n^2 log n)
3 er best