COMP90038
Algorithms and Complexity
Lecture 4: Analysis of Algorithms (with thanks to Harald Søndergaard)
DMD 8.17 (Level 8, Doug McDonell Bldg)
http://people.eng.unimelb.edu.au/tobym @tobycmurray
Last Time: Time Complexity
Measure input size by natural number n Measure execution time as number of basic
How to compare different t(n) ? Asymptotic growth rate
O(g(n)), Ω(g(n)), Θ(g(n))
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
• •
operations performed
Time complexity t(n) for an algorithm: number of
•
basic operations as a function of n
•
•
2
•
Establishing Growth Rate
•
•
•
A more common approach uses
In the last lecture we proved t(n) ∈ O(g(n)) for some n >n0 ⇒ t(n) < c ·g(n) for some c and n0.
•
cases of t and g, using the definition of O directly:
lim f(n) = { 0 n→∞ g(n) c
f grows asymptotically slower than g
f and g have same order of growth f grows asymptotically faster than g
3
Use this to show that 1000n ∈ O(n2)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
∞
4
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
1000n ∈ O(n2)
lim
1000n n2
1000
= =0
n
n→∞ lim
n→∞
So 1000n grows asymptotically slower than n2 Thus 1000n ∈ O(n2)
5
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
O, Ω, Θ
What this tells us about how f(n) relates to
•
f(n) lim g(n) =
{ 0 c
∞
f grows asymptotically slower than g
f and g have same order of growth f grows asymptotically faster than g
∈
)
∈
∈
Ω(
(
(
g
g
g
O(g(n)), Ω(g(n)) and Θ(g(n))
n→∞
f
f
f
(
(
(
n
n
n
)
)
)
O
Θ
(
(
(
n
n
n
)
)
)
)
)
L’Hôpital’s Rule
lim t(n) = lim t′(n) h→∞ g(n) h→∞ g′(n)
where t’ and g’ are the derivatives of t and g For example, show that log2 n grows slower than
•
lim n→∞
log n 2
1 (loge 2)n
n =lim 1⋅1⋅2n
= lim n→∞
1 2n
n→∞(log2 n ) e
n
= 2 lim n = 2 lim 1 =0
6
loge 2 n→∞ n loge 2 n→∞ n
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
7
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Example:
Finding Largest Element in an Array
A:
max: 246293
0123456 A[i]
(where n is length of the array)
23
12
42
6
69
18
3
8
Example:
Finding Largest Element in an Array
(where n is length of the array)
Size of input, n: length of the array
Basic operation: comparison “A[i] > max”
Count the number of basic operations executed for an array of size n:
n−1
C(n) = ∑ 1 = ((n − 1) − 1 + 1) = n − 1 ∈ Θ(n)
i=1
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Example: Selection Sort
23
12
42
6
69
18
3
0123456
A[i] A[j]
9 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
min: 3601
Example: Selection Sort
3
12
42
6
69
18
23
0123456
A[i]
10 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
min: 036
Example: Selection Sort
3
12
42
6
69
18
23
0123456
A[i] A[j]
11 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
min: 13
Example: Selection Sort
3
6
42
12
69
18
23
0123456
A[i]
12 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
min: 03
Example: Selection Sort
Basic operation: comparison A[j] < A[min]
n−2 n−1 n−2 n−2 n−2 C(n) =∑ ∑ 1 = ∑ (n − 1 − i) = ∑ (n − 1) − ∑ i
i=0 j=i+1
=(n−1)2−(n−2)(n−1) =n(n−1)∈Θ(n2)
22
Input size n: length of the array
i=0 i=0 i=0
13 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Example: Matrix Multiplication
i: 0
j: 0 k:10
57 82 1403
34 96
ABC
14 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Example: Matrix Multiplication
i: 0
j: 1 k:10
57 82 10351020
34 96
ABC
15 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Example: Matrix Multiplication
Basic operation: multiplication A[i,k] * B[k,j]
n−1 n−1 n−1 M(n) = ∑∑∑1
i=0 j=0 k=0
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Example: Matrix Multiplication
n−1 n−1 n−1 M(n) = ∑∑∑1
i=0 j=0 k=0
n−1 n−1 n−1 n−1 n−1 n−1 =∑∑((n−1)−0+1) =∑∑n =∑∑(n⋅1)
i=0 j=0
i=0
= n3
∈ Θ(n3)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
i=0 j=0
i=0 j=0
17
n−1 2 =∑ n⋅∑1 =∑n
n−1 n−1 i=0 j=0
Analysing Recursive Algorithms
F(5) =F(4)⋅5
= (F(3) ⋅ 4) ⋅ 5
= ((F(2) ⋅ 3) ⋅ 4) ⋅ 5
= (((F(1) ⋅ 2) ⋅ 3) ⋅ 4) ⋅ 5
= ((((F(0) ⋅ 1) ⋅ 2) ⋅ 3) ⋅ 4) ⋅ 5 = ((((1 ⋅ 1) ⋅ 2) ⋅ 3) ⋅ 4) ⋅ 5
= 5!
18 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Analysing Recursive Algorithms
We express the cost recursively (as a recurrence relation) M(0)= 0
M(n)= M(n−1)+1
Need to express M(n) in closed form (i.e. non-recursively)
Try: “telescoping” aka “backward substitution” 19 Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Basic operation: multiplication
Telescoping
(aka Backward Substitution)
M(n) = M(n − 1) + 1 What is M(n-1) ?
M(n)= (M(n−2)+1)+1 = M(n − 2) + 2
M(0) = 0
M(n − 1) = M((n − 1) − 1) + 1
= (M(n − 3) + 1) + 2 = M(n − 3) + 3
= M(n − 2) + 1 Closed form:
20
...
= M(n − n) + n
M(n) = n Complexity:
= M(0) + n
M(n) ∈ Θ(n) Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
=n
21
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Example:
Binary Search in Sorted Array
A:
BinSearch(A,0,6,41) BinSearch(A,4,6,41)
0123456
lo: 0
hi: 6 key: 41
mid: 3
4
9
13
22
41
83
96
22
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Example:
Binary Search in Sorted Array
A:
BinSearch(A,4,6,41) BinSearch(A,4,4,41)
0123456
lo: 4
hi: 6 key: 41
mid: 5
4
9
13
22
41
83
96
23
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Example:
Binary Search in Sorted Array
A:
BinSearch(A,4,4,41) returns 4
0123456
lo: 4
hi: 4 key: 41
mid: 4
4
9
13
22
41
83
96
Example:
Binary Search in Sorted Array
Basic operation: key comparison A[mid] = key
C(n) = C(n/2) + 1
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
C(0) = 0
Telescoping
A smoothness rule allows us to assume that n is a power of 2
C(0) = 0 C(n) = C(n/2) + 1
C(n) = C(n/2) + 1
= (C(n/4) + 1) + 1
= ((C(n/8) + 1) + 1) + 1 ...
C(n) ∈ Θ(log n) Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
= C(n/n) + log2 n
= (C(0) + 1) + log2 n = 1 + log2 n
Logarithmic Functions Have Same Rate of Growth
In O, Ω, Θ, expressions we can just write “log” for any logarithmic function no matter what the base is
Asymptotically, all logarithmic behaviour is the same, since
loga x = (loga b)(logb x)
lim logan = lim (loga b)(logb n) = (loga b) lim 1 = loga b
n→∞ logbn n→∞ logb n n→∞
26
log nc ∈ Θ(log n) Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
So, e.g.:
Also, since log nc = c ⋅ log n
Θ(logan) = Θ(logbn)
Back to Euclid
Running time is linear in size (in bits) of input, i.e. O(log(m + n))
since the value of m (and n) is at least halved in every two iterations.
Why? After two iterations, m becomes m mod n; also
1