blob: a6e560cfcfbfecae2acb9b20713a588f4d49c41a (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
|
# Opgave 1
## Exercise 9.2
**T(n) = 3T(n/2) + n**
a = 3
b = 2
d(n) = n
a ? d(b) -> 3 > 2
Svaret er derfor O(n^log2(3)) = O(n^1.59)
**T(n) = 3T(n/2) + n^2**
3 ? 2^2 -> 3 < 4
d(n) = n^2 hvilket betyder at O(n^2)
**T(n) = 8T(n/2) + n^2**
8 ? 2^3 -> 8 = 8
d(n) = n^3 hvilket betyder at O(n^3 log2(n))
## Evercise 9.3
**T(n) = 4T(n/3) + n**
a = 4
b = 3
d(n) = n
4 ? 3 -> 4 > 3
Derfor er svaret O(n^log3(4)) = O(n^1.26)
**T(n) = 4T(n/3) + n^2**
4 ? 3^2 -> 4 < 9
d(n) = n^2 hvilket betyder at O(n^2)
**T(n) = 9T(n/3) + n^2**
9 ? 3^2 -> 9 = 9
d(n) = n^2 hvilket betyder at O(n^2 log2(n))
|
