04.key
http://people.eng.unimelb.edu.au/tobym
@tobycmurray
toby.murray@unimelb.edu.au
DMD 8.17 (Level 8, Doug McDonell Bldg)
Toby Murray
COMP90038
Algorithms and Complexity
Lecture 4: Analysis of Algorithms
(with thanks to Harald Søndergaard)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Last Time: Time Complexity
• Measure input size by natural number n
• Measure execution time as number of basic
operations performed
• Time complexity t(n) for an algorithm: number of
basic operations as a function of n
• How to compare different t(n) ?
• Asymptotic growth rate
• O(g(n)), Ω(g(n)), Θ(g(n))
2
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Last Time: Time Complexity
• Measure input size by natural number n
• Measure execution time as number of basic
operations performed
• Time complexity t(n) for an algorithm: number of
basic operations as a function of n
• How to compare different t(n) ?
• Asymptotic growth rate
• O(g(n)), Ω(g(n)), Θ(g(n))
2
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Last Time: Time Complexity
• Measure input size by natural number n
• Measure execution time as number of basic
operations performed
• Time complexity t(n) for an algorithm: number of
basic operations as a function of n
• How to compare different t(n) ?
• Asymptotic growth rate
• O(g(n)), Ω(g(n)), Θ(g(n))
2
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Last Time: Time Complexity
• Measure input size by natural number n
• Measure execution time as number of basic
operations performed
• Time complexity t(n) for an algorithm: number of
basic operations as a function of n
• How to compare different t(n) ?
• Asymptotic growth rate
• O(g(n)), Ω(g(n)), Θ(g(n))
2
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Last Time: Time Complexity
• Measure input size by natural number n
• Measure execution time as number of basic
operations performed
• Time complexity t(n) for an algorithm: number of
basic operations as a function of n
• How to compare different t(n) ?
• Asymptotic growth rate
• O(g(n)), Ω(g(n)), Θ(g(n))
2
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Last Time: Time Complexity
• Measure input size by natural number n
• Measure execution time as number of basic
operations performed
• Time complexity t(n) for an algorithm: number of
basic operations as a function of n
• How to compare different t(n) ?
• Asymptotic growth rate
• O(g(n)), Ω(g(n)), Θ(g(n))
2
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Last Time: Time Complexity
• Measure input size by natural number n
• Measure execution time as number of basic
operations performed
• Time complexity t(n) for an algorithm: number of
basic operations as a function of n
• How to compare different t(n) ?
• Asymptotic growth rate
• O(g(n)), Ω(g(n)), Θ(g(n))
2
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Last Time: Time Complexity
• Measure input size by natural number n
• Measure execution time as number of basic
operations performed
• Time complexity t(n) for an algorithm: number of
basic operations as a function of n
• How to compare different t(n) ?
• Asymptotic growth rate
• O(g(n)), Ω(g(n)), Θ(g(n))
2
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Last Time: Time Complexity
• Measure input size by natural number n
• Measure execution time as number of basic
operations performed
• Time complexity t(n) for an algorithm: number of
basic operations as a function of n
• How to compare different t(n) ?
• Asymptotic growth rate
• O(g(n)), Ω(g(n)), Θ(g(n))
2
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Last Time: Time Complexity
• Measure input size by natural number n
• Measure execution time as number of basic
operations performed
• Time complexity t(n) for an algorithm: number of
basic operations as a function of n
• How to compare different t(n) ?
• Asymptotic growth rate
• O(g(n)), Ω(g(n)), Θ(g(n))
2
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Last Time: Time Complexity
• Measure input size by natural number n
• Measure execution time as number of basic
operations performed
• Time complexity t(n) for an algorithm: number of
basic operations as a function of n
• How to compare different t(n) ?
• Asymptotic growth rate
• O(g(n)), Ω(g(n)), Θ(g(n))
2
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Last Time: Time Complexity
• Measure input size by natural number n
• Measure execution time as number of basic
operations performed
• Time complexity t(n) for an algorithm: number of
basic operations as a function of n
• How to compare different t(n) ?
• Asymptotic growth rate
• O(g(n)), Ω(g(n)), Θ(g(n))
2
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Establishing Growth Rate
• In the last lecture we proved t(n) ∈ O(g(n)) for some
cases of t and g, using the definition of O directly:
n >n0 ⇒ t(n) < c ·g(n) for some c and n0.
• A more common approach uses
• lim =
• Use this to show that 1000n ∈ O(n2)
3
n→∞
f(n)
g(n) { 0 f grows asymptotically slower than gc f and g have same order of growth∞ f grows asymptotically faster than g
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
1000n
1000n ∈ O(n2)
4
n→∞
lim
n2
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
1000n
1000n ∈ O(n2)
4
n→∞
lim
n2
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
1000n
1000n ∈ O(n2)
4
n→∞
lim
n2
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
1000n
1000n ∈ O(n2)
4
n→∞
lim
n2
= 1000n→∞lim n
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
1000n
1000n ∈ O(n2)
4
n→∞
lim
n2
= 1000n→∞lim n
= 0
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
1000n
1000n ∈ O(n2)
4
n→∞
lim
n2
= 1000n→∞lim n
= 0
So 1000n grows asymptotically slower than n2
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
1000n
1000n ∈ O(n2)
4
n→∞
lim
n2
= 1000n→∞lim n
= 0
So 1000n grows asymptotically slower than n2
Thus 1000n ∈ O(n2)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
O, Ω, Θ
• lim =
5
n→∞
f(n)
g(n) { 0 f grows asymptotically slower than gc f and g have same order of growth∞ f grows asymptotically faster than g
What this tells us about how f(n) relates to
O(g(n)), Ω(g(n)) and Θ(g(n))
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
O, Ω, Θ
• lim =
5
n→∞
f(n)
g(n) { 0 f grows asymptotically slower than gc f and g have same order of growth∞ f grows asymptotically faster than g
What this tells us about how f(n) relates to
O(g(n)), Ω(g(n)) and Θ(g(n))
f(n) ∈ O(g(n))
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
O, Ω, Θ
• lim =
5
n→∞
f(n)
g(n) { 0 f grows asymptotically slower than gc f and g have same order of growth∞ f grows asymptotically faster than g
What this tells us about how f(n) relates to
O(g(n)), Ω(g(n)) and Θ(g(n))
f(n) ∈ O(g(n))
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
O, Ω, Θ
• lim =
5
n→∞
f(n)
g(n) { 0 f grows asymptotically slower than gc f and g have same order of growth∞ f grows asymptotically faster than g
What this tells us about how f(n) relates to
O(g(n)), Ω(g(n)) and Θ(g(n))
f(n) ∈ O(g(n))
f(n) ∈ Ω(g(n))
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
O, Ω, Θ
• lim =
5
n→∞
f(n)
g(n) { 0 f grows asymptotically slower than gc f and g have same order of growth∞ f grows asymptotically faster than g
What this tells us about how f(n) relates to
O(g(n)), Ω(g(n)) and Θ(g(n))
f(n) ∈ O(g(n))
f(n) ∈ Ω(g(n))
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
O, Ω, Θ
• lim =
5
n→∞
f(n)
g(n) { 0 f grows asymptotically slower than gc f and g have same order of growth∞ f grows asymptotically faster than g
What this tells us about how f(n) relates to
O(g(n)), Ω(g(n)) and Θ(g(n))
f(n) ∈ O(g(n))
f(n) ∈ Ω(g(n))
f(n) ∈ Θ(g(n))
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
O, Ω, Θ
• lim =
5
n→∞
f(n)
g(n) { 0 f grows asymptotically slower than gc f and g have same order of growth∞ f grows asymptotically faster than g
What this tells us about how f(n) relates to
O(g(n)), Ω(g(n)) and Θ(g(n))
f(n) ∈ O(g(n))
f(n) ∈ Ω(g(n))
f(n) ∈ Θ(g(n))
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
L’Hôpital’s Rule
6
lim
h→∞
t(n)
g(n)
= lim
h→∞
t′�(n)
g′ �(n)
where t’ and g’ are the derivatives of t and g
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
L’Hôpital’s Rule
• For example, show that log2 n grows slower than
6
lim
h→∞
t(n)
g(n)
= lim
h→∞
t′�(n)
g′ �(n)
n
where t’ and g’ are the derivatives of t and g
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
L’Hôpital’s Rule
• For example, show that log2 n grows slower than
6
lim
h→∞
t(n)
g(n)
= lim
h→∞
t′�(n)
g′ �(n)
n
lim
n→∞
log2 n
n
where t’ and g’ are the derivatives of t and g
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
L’Hôpital’s Rule
• For example, show that log2 n grows slower than
6
lim
h→∞
t(n)
g(n)
= lim
h→∞
t′�(n)
g′ �(n)
n
lim
n→∞
log2 n
n
= lim
n→∞
(loge 2)
1
n
1
2 n
where t’ and g’ are the derivatives of t and g
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
L’Hôpital’s Rule
• For example, show that log2 n grows slower than
6
lim
h→∞
t(n)
g(n)
= lim
h→∞
t′�(n)
g′ �(n)
n
lim
n→∞
log2 n
n
= lim
n→∞
(loge 2)
1
n
1
2 n
= lim
n→∞ ((loge 2)
1
n
⋅ 2 n)
where t’ and g’ are the derivatives of t and g
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
L’Hôpital’s Rule
• For example, show that log2 n grows slower than
6
lim
h→∞
t(n)
g(n)
= lim
h→∞
t′�(n)
g′ �(n)
n
lim
n→∞
log2 n
n
= lim
n→∞
(loge 2)
1
n
1
2 n
= lim
n→∞ ((loge 2)
1
n
⋅ 2 n)
= 2 loge 2 lim
n→∞
n
n
where t’ and g’ are the derivatives of t and g
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
L’Hôpital’s Rule
• For example, show that log2 n grows slower than
6
lim
h→∞
t(n)
g(n)
= lim
h→∞
t′�(n)
g′ �(n)
n
lim
n→∞
log2 n
n
= lim
n→∞
(loge 2)
1
n
1
2 n
= lim
n→∞ ((loge 2)
1
n
⋅ 2 n)
= 2 loge 2 lim
n→∞
n
n
= 2 loge 2 lim
n→∞
1
n
where t’ and g’ are the derivatives of t and g
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
L’Hôpital’s Rule
• For example, show that log2 n grows slower than
6
lim
h→∞
t(n)
g(n)
= lim
h→∞
t′�(n)
g′ �(n)
n
lim
n→∞
log2 n
n
= lim
n→∞
(loge 2)
1
n
1
2 n
= lim
n→∞ ((loge 2)
1
n
⋅ 2 n)
= 2 loge 2 lim
n→∞
n
n
= 2 loge 2 lim
n→∞
1
n
= 0
where t’ and g’ are the derivatives of t and g
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Example:
Finding Largest Element in an Array
7
23 12 42 6 69 18 3A: max: 23
(where n is length of
the array)
0 1 2 3 4 5 6
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Example:
Finding Largest Element in an Array
7
23 12 42 6 69 18 3A: max: 23
(where n is length of
the array)
0 1 2 3 4 5 6
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Example:
Finding Largest Element in an Array
7
23 12 42 6 69 18 3A: max: 23
A[i]
(where n is length of
the array)
0 1 2 3 4 5 6
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Example:
Finding Largest Element in an Array
7
23 12 42 6 69 18 3A: max: 23
A[i]
(where n is length of
the array)
0 1 2 3 4 5 6
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Example:
Finding Largest Element in an Array
7
23 12 42 6 69 18 3A: max: 23
A[i]
42
(where n is length of
the array)
0 1 2 3 4 5 6
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Example:
Finding Largest Element in an Array
7
23 12 42 6 69 18 3A: max: 23
A[i]
42
(where n is length of
the array)
0 1 2 3 4 5 6
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Example:
Finding Largest Element in an Array
7
23 12 42 6 69 18 3A: max: 23
A[i]
42
(where n is length of
the array)
0 1 2 3 4 5 6
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Example:
Finding Largest Element in an Array
7
23 12 42 6 69 18 3A: max: 23
A[i]
4269
(where n is length of
the array)
0 1 2 3 4 5 6
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Example:
Finding Largest Element in an Array
7
23 12 42 6 69 18 3A: max: 23
A[i]
4269
(where n is length of
the array)
0 1 2 3 4 5 6
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Example:
Finding Largest Element in an Array
7
23 12 42 6 69 18 3A: max: 23
A[i]
4269
(where n is length of
the array)
0 1 2 3 4 5 6
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
C(n) =
Example:
Finding Largest Element in an Array
8
(where n is length of
the array)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
C(n) =
Example:
Finding Largest Element in an Array
8
(where n is length of
the array)
Size of input, n:
length of the array
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
C(n) =
Example:
Finding Largest Element in an Array
8
(where n is length of
the array)
Size of input, n:
length of the array
Basic operation: comparison “A[i] > max”
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
C(n) =
Example:
Finding Largest Element in an Array
8
(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:
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
C(n) =
Example:
Finding Largest Element in an Array
8
(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
∑
i=1
1 = ((n − 1) − 1 + 1) = n − 1 ∈ Θ(n)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
C(n) =
Example:
Finding Largest Element in an Array
8
(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
∑
i=1
1 = ((n − 1) − 1 + 1) = n − 1 ∈ Θ(n)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
C(n) =
Example:
Finding Largest Element in an Array
8
(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
∑
i=1
1 = ((n − 1) − 1 + 1) = n − 1 ∈ Θ(n)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
C(n) =
Example:
Finding Largest Element in an Array
8
(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
∑
i=1
1 = ((n − 1) − 1 + 1) = n − 1 ∈ Θ(n)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
C(n) =
Example:
Finding Largest Element in an Array
8
(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
∑
i=1
1 = ((n − 1) − 1 + 1) = n − 1 ∈ Θ(n)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
C(n) =
Example:
Finding Largest Element in an Array
8
(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
∑
i=1
1 = ((n − 1) − 1 + 1) = n − 1 ∈ Θ(n)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Example: Selection Sort
9
23 12 42 6 69 18 3
0 1 2 3 4 5 6
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Example: Selection Sort
9
23 12 42 6 69 18 3
A[i]
0 1 2 3 4 5 6
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Example: Selection Sort
9
23 12 42 6 69 18 3
A[i]
min: 0
0 1 2 3 4 5 6
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Example: Selection Sort
9
23 12 42 6 69 18 3
A[i]
min:
A[j]
0
0 1 2 3 4 5 6
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Example: Selection Sort
9
23 12 42 6 69 18 3
A[i]
min:
A[j]
0
0 1 2 3 4 5 6
1
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Example: Selection Sort
9
23 12 42 6 69 18 3
A[i]
min:
A[j]
0
0 1 2 3 4 5 6
1
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Example: Selection Sort
9
23 12 42 6 69 18 3
A[i]
min:
A[j]
0
0 1 2 3 4 5 6
1
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Example: Selection Sort
9
23 12 42 6 69 18 3
A[i]
min:
A[j]
0
0 1 2 3 4 5 6
13
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Example: Selection Sort
9
23 12 42 6 69 18 3
A[i]
min:
A[j]
0
0 1 2 3 4 5 6
13
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Example: Selection Sort
9
23 12 42 6 69 18 3
A[i]
min:
A[j]
0
0 1 2 3 4 5 6
13
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Example: Selection Sort
9
23 12 42 6 69 18 3
A[i]
min:
A[j]
0
0 1 2 3 4 5 6
13
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Example: Selection Sort
9
23 12 42 6 69 18 3
A[i]
min:
A[j]
0
0 1 2 3 4 5 6
136
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Example: Selection Sort
10
3 12 42 6 69 18 23
A[i]
min: 03
0 1 2 3 4 5 6
6
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Example: Selection Sort
10
3 12 42 6 69 18 23
A[i]
min: 03
0 1 2 3 4 5 6
6
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Example: Selection Sort
11
3 12 42 6 69 18 23
A[i]
0 1 2 3 4 5 6
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Example: Selection Sort
11
3 12 42 6 69 18 23
A[i]
min: 1
0 1 2 3 4 5 6
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Example: Selection Sort
11
3 12 42 6 69 18 23
A[i]
min:
A[j]
1
0 1 2 3 4 5 6
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Example: Selection Sort
11
3 12 42 6 69 18 23
A[i]
min:
A[j]
1
0 1 2 3 4 5 6
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Example: Selection Sort
11
3 12 42 6 69 18 23
A[i]
min:
A[j]
13
0 1 2 3 4 5 6
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Example: Selection Sort
11
3 12 42 6 69 18 23
A[i]
min:
A[j]
13
0 1 2 3 4 5 6
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Example: Selection Sort
11
3 12 42 6 69 18 23
A[i]
min:
A[j]
13
0 1 2 3 4 5 6
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Example: Selection Sort
11
3 12 42 6 69 18 23
A[i]
min:
A[j]
13
0 1 2 3 4 5 6
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Example: Selection Sort
12
3 6 42 12 69 18 23
A[i]
min: 03
0 1 2 3 4 5 6
3
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Example: Selection Sort
12
3 6 42 12 69 18 23
A[i]
min: 03
0 1 2 3 4 5 6
3
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Example: Selection Sort
13
Input size n: length
of the array
Basic operation:
comparison A[j] < A[min]
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Example: Selection Sort
13
Input size n: length
of the array
Basic operation:
comparison A[j] < A[min]
C(n) =
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Example: Selection Sort
13
Input size n: length
of the array
Basic operation:
comparison A[j] < A[min]
C(n) =
n−2
∑
i=0
n−1
∑
j=i+1
1
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Example: Selection Sort
13
Input size n: length
of the array
Basic operation:
comparison A[j] < A[min]
C(n) =
n−2
∑
i=0
n−1
∑
j=i+1
1 =
n−2
∑
i=0
(n − 1 − i)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Example: Selection Sort
13
Input size n: length
of the array
Basic operation:
comparison A[j] < A[min]
C(n) =
n−2
∑
i=0
n−1
∑
j=i+1
1 =
n−2
∑
i=0
(n − 1 − i) =
n−2
∑
i=0
(n − 1) −
n−2
∑
i=0
i
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Example: Selection Sort
13
Input size n: length
of the array
Basic operation:
comparison A[j] < A[min]
C(n) =
n−2
∑
i=0
n−1
∑
j=i+1
1 =
n−2
∑
i=0
(n − 1 − i) =
n−2
∑
i=0
(n − 1) −
n−2
∑
i=0
i
= (n − 1)2 −
(n − 2)(n − 1)
2
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Example: Selection Sort
13
Input size n: length
of the array
Basic operation:
comparison A[j] < A[min]
C(n) =
n−2
∑
i=0
n−1
∑
j=i+1
1 =
n−2
∑
i=0
(n − 1 − i) =
n−2
∑
i=0
(n − 1) −
n−2
∑
i=0
i
= (n − 1)2 −
(n − 2)(n − 1)
2
=
n(n − 1)
2
∈ Θ(n2)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Example: Matrix Multiplication
14
5 7
3 4
8 2
9 6
A B C
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Example: Matrix Multiplication
14
5 7
3 4
8 2
9 6
A B C
i: 0
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Example: Matrix Multiplication
14
5 7
3 4
8 2
9 6
A B C
i: 0
j: 0
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Example: Matrix Multiplication
14
5 7
3 4
8 2
9 6
A B C
0
i: 0
j: 0
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Example: Matrix Multiplication
14
5 7
3 4
8 2
9 6
A B C
0
i: 0
j: 0
k: 0
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Example: Matrix Multiplication
14
5 7
3 4
8 2
9 6
A B C
0
i: 0
j: 0
k: 0
40
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Example: Matrix Multiplication
14
5 7
3 4
8 2
9 6
A B C
0
i: 0
j: 0
k: 0
40
k: 1
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Example: Matrix Multiplication
14
5 7
3 4
8 2
9 6
A B C
0
i: 0
j: 0
k: 0
40
k: 1
103
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Example: Matrix Multiplication
15
5 7
3 4
8 2
9 6
A B C
i: 0
j: 1
103
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Example: Matrix Multiplication
15
5 7
3 4
8 2
9 6
A B C
0
i: 0
j: 1
103
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Example: Matrix Multiplication
15
5 7
3 4
8 2
9 6
A B C
0
i: 0
j: 1
k: 0
103
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Example: Matrix Multiplication
15
5 7
3 4
8 2
9 6
A B C
0
i: 0
j: 1
k: 0
10103
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Example: Matrix Multiplication
15
5 7
3 4
8 2
9 6
A B C
0
i: 0
j: 1
k: 0
10
k: 1
103
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Example: Matrix Multiplication
15
5 7
3 4
8 2
9 6
A B C
0
i: 0
j: 1
k: 0
10
k: 1
103 52
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Example: Matrix Multiplication
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Example: Matrix Multiplication
Basic operation: multiplication A[i,k] * B[k,j]
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Example: Matrix Multiplication
Basic operation: multiplication A[i,k] * B[k,j]
M(n) =
n−1
∑
i=0
n−1
∑
j=0
n−1
∑
k=0
1
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Example: Matrix Multiplication
Basic operation: multiplication A[i,k] * B[k,j]
M(n) =
n−1
∑
i=0
n−1
∑
j=0
n−1
∑
k=0
1
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Example: Matrix Multiplication
Basic operation: multiplication A[i,k] * B[k,j]
M(n) =
n−1
∑
i=0
n−1
∑
j=0
n−1
∑
k=0
1
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Example: Matrix Multiplication
Basic operation: multiplication A[i,k] * B[k,j]
M(n) =
n−1
∑
i=0
n−1
∑
j=0
n−1
∑
k=0
1
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Example: Matrix Multiplication
Basic operation: multiplication A[i,k] * B[k,j]
M(n) =
n−1
∑
i=0
n−1
∑
j=0
n−1
∑
k=0
1
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Example: Matrix Multiplication
17
M(n) =
n−1
∑
i=0
n−1
∑
j=0
n−1
∑
k=0
1
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Example: Matrix Multiplication
17
M(n) =
n−1
∑
i=0
n−1
∑
j=0
n−1
∑
k=0
1
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Example: Matrix Multiplication
17
M(n) =
n−1
∑
i=0
n−1
∑
j=0
n−1
∑
k=0
1
=
n−1
∑
i=0
n−1
∑
j=0
((n − 1) − 0 + 1)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Example: Matrix Multiplication
17
M(n) =
n−1
∑
i=0
n−1
∑
j=0
n−1
∑
k=0
1
=
n−1
∑
i=0
n−1
∑
j=0
((n − 1) − 0 + 1) =
n−1
∑
i=0
n−1
∑
j=0
n
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Example: Matrix Multiplication
17
M(n) =
n−1
∑
i=0
n−1
∑
j=0
n−1
∑
k=0
1
=
n−1
∑
i=0
n−1
∑
j=0
((n − 1) − 0 + 1) =
n−1
∑
i=0
n−1
∑
j=0
n =
n−1
∑
i=0
n−1
∑
j=0
(n ⋅ 1)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Example: Matrix Multiplication
17
M(n) =
n−1
∑
i=0
n−1
∑
j=0
n−1
∑
k=0
1
=
n−1
∑
i=0
n−1
∑
j=0
((n − 1) − 0 + 1) =
n−1
∑
i=0
n−1
∑
j=0
n =
n−1
∑
i=0
n−1
∑
j=0
(n ⋅ 1)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Example: Matrix Multiplication
17
M(n) =
n−1
∑
i=0
n−1
∑
j=0
n−1
∑
k=0
1
=
n−1
∑
i=0
n−1
∑
j=0
((n − 1) − 0 + 1) =
n−1
∑
i=0
n−1
∑
j=0
n =
n−1
∑
i=0
n−1
∑
j=0
(n ⋅ 1)
=
n−1
∑
i=0
n ⋅
n−1
∑
j=0
1
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Example: Matrix Multiplication
17
M(n) =
n−1
∑
i=0
n−1
∑
j=0
n−1
∑
k=0
1
=
n−1
∑
i=0
n−1
∑
j=0
((n − 1) − 0 + 1) =
n−1
∑
i=0
n−1
∑
j=0
n =
n−1
∑
i=0
n−1
∑
j=0
(n ⋅ 1)
=
n−1
∑
i=0
n ⋅
n−1
∑
j=0
1 =
n−1
∑
i=0
n2
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Example: Matrix Multiplication
17
M(n) =
n−1
∑
i=0
n−1
∑
j=0
n−1
∑
k=0
1
=
n−1
∑
i=0
n−1
∑
j=0
((n − 1) − 0 + 1) =
n−1
∑
i=0
n−1
∑
j=0
n =
n−1
∑
i=0
n−1
∑
j=0
(n ⋅ 1)
=
n−1
∑
i=0
n ⋅
n−1
∑
j=0
1 =
n−1
∑
i=0
n2
= n3
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Example: Matrix Multiplication
17
M(n) =
n−1
∑
i=0
n−1
∑
j=0
n−1
∑
k=0
1
=
n−1
∑
i=0
n−1
∑
j=0
((n − 1) − 0 + 1) =
n−1
∑
i=0
n−1
∑
j=0
n =
n−1
∑
i=0
n−1
∑
j=0
(n ⋅ 1)
=
n−1
∑
i=0
n ⋅
n−1
∑
j=0
1 =
n−1
∑
i=0
n2
= n3
∈ Θ(n3)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Analysing Recursive
Algorithms
18
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Analysing Recursive
Algorithms
18
F(5)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Analysing Recursive
Algorithms
18
F(5) = F(4) ⋅ 5
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Analysing Recursive
Algorithms
18
F(5) = F(4) ⋅ 5
= (F(3) ⋅ 4) ⋅ 5
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Analysing Recursive
Algorithms
18
F(5) = F(4) ⋅ 5
= (F(3) ⋅ 4) ⋅ 5
= ((F(2) ⋅ 3) ⋅ 4) ⋅ 5
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Analysing Recursive
Algorithms
18
F(5) = F(4) ⋅ 5
= (F(3) ⋅ 4) ⋅ 5
= ((F(2) ⋅ 3) ⋅ 4) ⋅ 5
= (((F(1) ⋅ 2) ⋅ 3) ⋅ 4) ⋅ 5
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Analysing Recursive
Algorithms
18
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
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Analysing Recursive
Algorithms
18
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
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Analysing Recursive
Algorithms
18
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!
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Analysing Recursive
Algorithms
19
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Analysing Recursive
Algorithms
19
Basic operation:
multiplication
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Analysing Recursive
Algorithms
19
Basic operation:
multiplication
We express the cost recursively (as a recurrence relation)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Analysing Recursive
Algorithms
19
Basic operation:
multiplication
We express the cost recursively (as a recurrence relation)
M(0) =
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Analysing Recursive
Algorithms
19
Basic operation:
multiplication
We express the cost recursively (as a recurrence relation)
M(0) = 0
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Analysing Recursive
Algorithms
19
Basic operation:
multiplication
We express the cost recursively (as a recurrence relation)
M(0) = 0
M(n) =
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Analysing Recursive
Algorithms
19
Basic operation:
multiplication
We express the cost recursively (as a recurrence relation)
M(0) = 0
M(n) = M(n − 1) + 1
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Analysing Recursive
Algorithms
19
Basic operation:
multiplication
We express the cost recursively (as a recurrence relation)
M(0) = 0
M(n) = M(n − 1) + 1
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Analysing Recursive
Algorithms
19
Basic operation:
multiplication
We express the cost recursively (as a recurrence relation)
M(0) = 0
M(n) = M(n − 1) + 1
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Analysing Recursive
Algorithms
19
Basic operation:
multiplication
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)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Analysing Recursive
Algorithms
19
Basic operation:
multiplication
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”
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Telescoping
(aka Backward Substitution)
20
M(0) = 0M(n) = M(n − 1) + 1
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Telescoping
(aka Backward Substitution)
20
M(0) = 0M(n) = M(n − 1) + 1
What is M(n-1) ?
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Telescoping
(aka Backward Substitution)
20
M(0) = 0M(n) = M(n − 1) + 1
What is M(n-1) ? M(n − 1) = M((n − 1) − 1) + 1
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Telescoping
(aka Backward Substitution)
20
M(0) = 0M(n) = M(n − 1) + 1
What is M(n-1) ? M(n − 1) = M((n − 1) − 1) + 1
= M(n − 2) + 1
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Telescoping
(aka Backward Substitution)
20
M(0) = 0M(n) = M(n − 1) + 1
What is M(n-1) ? M(n − 1) = M((n − 1) − 1) + 1
= M(n − 2) + 1
M(n) =
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Telescoping
(aka Backward Substitution)
20
M(0) = 0M(n) = M(n − 1) + 1
What is M(n-1) ? M(n − 1) = M((n − 1) − 1) + 1
= M(n − 2) + 1
M(n) = (M(n − 2) + 1) + 1
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Telescoping
(aka Backward Substitution)
20
M(0) = 0M(n) = M(n − 1) + 1
What is M(n-1) ? M(n − 1) = M((n − 1) − 1) + 1
= M(n − 2) + 1
M(n) = (M(n − 2) + 1) + 1
= M(n − 2) + 2
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Telescoping
(aka Backward Substitution)
20
M(0) = 0M(n) = M(n − 1) + 1
What is M(n-1) ? M(n − 1) = M((n − 1) − 1) + 1
= M(n − 2) + 1
M(n) = (M(n − 2) + 1) + 1
= M(n − 2) + 2
= (M(n − 3) + 1) + 2
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Telescoping
(aka Backward Substitution)
20
M(0) = 0M(n) = M(n − 1) + 1
What is M(n-1) ? M(n − 1) = M((n − 1) − 1) + 1
= M(n − 2) + 1
M(n) = (M(n − 2) + 1) + 1
= M(n − 2) + 2
= (M(n − 3) + 1) + 2
= M(n − 3) + 3
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Telescoping
(aka Backward Substitution)
20
M(0) = 0M(n) = M(n − 1) + 1
What is M(n-1) ? M(n − 1) = M((n − 1) − 1) + 1
= M(n − 2) + 1
M(n) = (M(n − 2) + 1) + 1
= M(n − 2) + 2
= (M(n − 3) + 1) + 2
= M(n − 3) + 3
…
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Telescoping
(aka Backward Substitution)
20
M(0) = 0M(n) = M(n − 1) + 1
What is M(n-1) ? M(n − 1) = M((n − 1) − 1) + 1
= M(n − 2) + 1
M(n) = (M(n − 2) + 1) + 1
= M(n − 2) + 2
= (M(n − 3) + 1) + 2
= M(n − 3) + 3
…
= M(n − n) + n
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Telescoping
(aka Backward Substitution)
20
M(0) = 0M(n) = M(n − 1) + 1
What is M(n-1) ? M(n − 1) = M((n − 1) − 1) + 1
= M(n − 2) + 1
M(n) = (M(n − 2) + 1) + 1
= M(n − 2) + 2
= (M(n − 3) + 1) + 2
= M(n − 3) + 3
…
= M(n − n) + n
= M(0) + n
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Telescoping
(aka Backward Substitution)
20
M(0) = 0M(n) = M(n − 1) + 1
What is M(n-1) ? M(n − 1) = M((n − 1) − 1) + 1
= M(n − 2) + 1
M(n) = (M(n − 2) + 1) + 1
= M(n − 2) + 2
= (M(n − 3) + 1) + 2
= M(n − 3) + 3
…
= M(n − n) + n
= M(0) + n
= n
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Telescoping
(aka Backward Substitution)
20
M(0) = 0M(n) = M(n − 1) + 1
What is M(n-1) ? M(n − 1) = M((n − 1) − 1) + 1
= M(n − 2) + 1
M(n) = (M(n − 2) + 1) + 1
= M(n − 2) + 2
= (M(n − 3) + 1) + 2
= M(n − 3) + 3
…
= M(n − n) + n
= M(0) + n
= n
Closed form:
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Telescoping
(aka Backward Substitution)
20
M(0) = 0M(n) = M(n − 1) + 1
What is M(n-1) ? M(n − 1) = M((n − 1) − 1) + 1
= M(n − 2) + 1
M(n) = (M(n − 2) + 1) + 1
= M(n − 2) + 2
= (M(n − 3) + 1) + 2
= M(n − 3) + 3
…
= M(n − n) + n
= M(0) + n
= n
Closed form:
M(n) = n
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Telescoping
(aka Backward Substitution)
20
M(0) = 0M(n) = M(n − 1) + 1
What is M(n-1) ? M(n − 1) = M((n − 1) − 1) + 1
= M(n − 2) + 1
M(n) = (M(n − 2) + 1) + 1
= M(n − 2) + 2
= (M(n − 3) + 1) + 2
= M(n − 3) + 3
…
= M(n − n) + n
= M(0) + n
= n
Closed form:
M(n) = n
Complexity:
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Telescoping
(aka Backward Substitution)
20
M(0) = 0M(n) = M(n − 1) + 1
What is M(n-1) ? M(n − 1) = M((n − 1) − 1) + 1
= M(n − 2) + 1
M(n) = (M(n − 2) + 1) + 1
= M(n − 2) + 2
= (M(n − 3) + 1) + 2
= M(n − 3) + 3
…
= M(n − n) + n
= M(0) + n
= n
Closed form:
M(n) = n
Complexity:
M(n) ∈ Θ(n)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Example:
Binary Search in Sorted Array
21
4 9 13 22 41 83 96A:
0 1 2 3 4 5 6
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Example:
Binary Search in Sorted Array
21
4 9 13 22 41 83 96A:
0 1 2 3 4 5 6
BinSearch(A,0,6,41)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Example:
Binary Search in Sorted Array
21
4 9 13 22 41 83 96A:
0 1 2 3 4 5 6
BinSearch(A,0,6,41)
lo: 0
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Example:
Binary Search in Sorted Array
21
4 9 13 22 41 83 96A:
0 1 2 3 4 5 6
BinSearch(A,0,6,41)
lo: 0
hi: 6
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Example:
Binary Search in Sorted Array
21
4 9 13 22 41 83 96A:
0 1 2 3 4 5 6
BinSearch(A,0,6,41)
lo: 0
hi: 6
key: 41
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Example:
Binary Search in Sorted Array
21
4 9 13 22 41 83 96A:
0 1 2 3 4 5 6
BinSearch(A,0,6,41)
lo: 0
hi: 6
key: 41
mid: 3
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Example:
Binary Search in Sorted Array
21
4 9 13 22 41 83 96A:
0 1 2 3 4 5 6
BinSearch(A,0,6,41)
lo: 0
hi: 6
key: 41
mid: 3
BinSearch(A,4,6,41)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Example:
Binary Search in Sorted Array
22
4 9 13 22 41 83 96A:
0 1 2 3 4 5 6
BinSearch(A,4,6,41)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Example:
Binary Search in Sorted Array
22
4 9 13 22 41 83 96A:
0 1 2 3 4 5 6
BinSearch(A,4,6,41)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Example:
Binary Search in Sorted Array
22
4 9 13 22 41 83 96A:
0 1 2 3 4 5 6
BinSearch(A,4,6,41)
lo: 4
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Example:
Binary Search in Sorted Array
22
4 9 13 22 41 83 96A:
0 1 2 3 4 5 6
BinSearch(A,4,6,41)
lo: 4
hi: 6
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Example:
Binary Search in Sorted Array
22
4 9 13 22 41 83 96A:
0 1 2 3 4 5 6
BinSearch(A,4,6,41)
lo: 4
hi: 6
key: 41
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Example:
Binary Search in Sorted Array
22
4 9 13 22 41 83 96A:
0 1 2 3 4 5 6
BinSearch(A,4,6,41)
lo: 4
hi: 6
key: 41
mid: 5
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Example:
Binary Search in Sorted Array
22
4 9 13 22 41 83 96A:
0 1 2 3 4 5 6
BinSearch(A,4,6,41)
lo: 4
hi: 6
key: 41
mid: 5
BinSearch(A,4,4,41)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Example:
Binary Search in Sorted Array
23
4 9 13 22 41 83 96A:
0 1 2 3 4 5 6
BinSearch(A,4,4,41)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Example:
Binary Search in Sorted Array
23
4 9 13 22 41 83 96A:
0 1 2 3 4 5 6
BinSearch(A,4,4,41)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Example:
Binary Search in Sorted Array
23
4 9 13 22 41 83 96A:
0 1 2 3 4 5 6
BinSearch(A,4,4,41)
lo: 4
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Example:
Binary Search in Sorted Array
23
4 9 13 22 41 83 96A:
0 1 2 3 4 5 6
BinSearch(A,4,4,41)
lo: 4
hi: 4
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Example:
Binary Search in Sorted Array
23
4 9 13 22 41 83 96A:
0 1 2 3 4 5 6
BinSearch(A,4,4,41)
lo: 4
hi: 4
key: 41
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Example:
Binary Search in Sorted Array
23
4 9 13 22 41 83 96A:
0 1 2 3 4 5 6
BinSearch(A,4,4,41)
lo: 4
hi: 4
key: 41
mid: 4
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Example:
Binary Search in Sorted Array
23
4 9 13 22 41 83 96A:
0 1 2 3 4 5 6
BinSearch(A,4,4,41)
lo: 4
hi: 4
key: 41
mid: 4
returns 4
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Example:
Binary Search in Sorted Array
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Example:
Binary Search in Sorted Array
Basic operation: key comparison A[mid] = key
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Example:
Binary Search in Sorted Array
Basic operation: key comparison A[mid] = key
C(0) =
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Example:
Binary Search in Sorted Array
Basic operation: key comparison A[mid] = key
C(0) = 0
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Example:
Binary Search in Sorted Array
Basic operation: key comparison A[mid] = key
C(0) = 0 C(n) = C(n/2) + 1
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Example:
Binary Search in Sorted Array
Basic operation: key comparison A[mid] = key
C(0) = 0 C(n) = C(n/2) + 1
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Telescoping
C(0) = 0 C(n) = C(n/2) + 1
A smoothness rule allows us to assume
that n is a power of 2
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Telescoping
C(0) = 0 C(n) = C(n/2) + 1
C(n) = C(n/2) + 1
A smoothness rule allows us to assume
that n is a power of 2
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Telescoping
C(0) = 0 C(n) = C(n/2) + 1
C(n) = C(n/2) + 1
= (C(n/4) + 1) + 1
A smoothness rule allows us to assume
that n is a power of 2
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Telescoping
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
A smoothness rule allows us to assume
that n is a power of 2
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Telescoping
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
…
A smoothness rule allows us to assume
that n is a power of 2
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Telescoping
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/n) + log2 n
A smoothness rule allows us to assume
that n is a power of 2
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Telescoping
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/n) + log2 n
A smoothness rule allows us to assume
that n is a power of 2
= (C(0) + 1) + log2 n
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Telescoping
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/n) + log2 n
A smoothness rule allows us to assume
that n is a power of 2
= (C(0) + 1) + log2 n
= 1 + log2 n
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Telescoping
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/n) + log2 n
A smoothness rule allows us to assume
that n is a power of 2
= (C(0) + 1) + log2 n
= 1 + log2 n
C(n) ∈ Θ(log n)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Logarithmic Functions
Have Same Rate of Growth
26
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)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Logarithmic Functions
Have Same Rate of Growth
26
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
n→∞
logan
logbn
= lim
n→∞
(loga b)(logb n)
logb n
= (loga b) lim
n→∞
1 = loga b
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Logarithmic Functions
Have Same Rate of Growth
26
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
n→∞
logan
logbn
= lim
n→∞
(loga b)(logb n)
logb n
= (loga b) lim
n→∞
1 = loga b
So, e.g.:
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Logarithmic Functions
Have Same Rate of Growth
26
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
n→∞
logan
logbn
= lim
n→∞
(loga b)(logb n)
logb n
= (loga b) lim
n→∞
1 = loga b
O(logan) = O(logbn)So, e.g.:
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Logarithmic Functions
Have Same Rate of Growth
26
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
n→∞
logan
logbn
= lim
n→∞
(loga b)(logb n)
logb n
= (loga b) lim
n→∞
1 = loga b
O(logan) = O(logbn)So, e.g.:
Also, since
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Logarithmic Functions
Have Same Rate of Growth
26
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
n→∞
logan
logbn
= lim
n→∞
(loga b)(logb n)
logb n
= (loga b) lim
n→∞
1 = loga b
O(logan) = O(logbn)So, e.g.:
Also, since log nc = c ⋅ log n
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Logarithmic Functions
Have Same Rate of Growth
26
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
n→∞
logan
logbn
= lim
n→∞
(loga b)(logb n)
logb n
= (loga b) lim
n→∞
1 = loga b
O(logan) = O(logbn)So, e.g.:
Also, since log nc = c ⋅ log n log nc ∈ O(log n)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Back to Euclid
27
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Back to Euclid
27
Running time is linear in size (in bits) of input, i.e.
O(log(m + n))
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Back to Euclid
27
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.
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Back to Euclid
27
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 < n < m ⟹ m mod n < m/2
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Summarising Reasoning
with Big-Oh
28
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Summarising Reasoning
with Big-Oh
28
Suppose
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Summarising Reasoning
with Big-Oh
28
Suppose t1(n) ∈ O(g1(n)) t2(n) ∈ O(g2(n))
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Summarising Reasoning
with Big-Oh
28
Suppose t1(n) ∈ O(g1(n)) t2(n) ∈ O(g2(n))
Then the following hold:
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Summarising Reasoning
with Big-Oh
28
Suppose
t1(n) + t2(n) ∈ O(max{g1(n), g2(n)})
t1(n) ∈ O(g1(n)) t2(n) ∈ O(g2(n))
Then the following hold:
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Summarising Reasoning
with Big-Oh
28
Suppose
t1(n) + t2(n) ∈ O(max{g1(n), g2(n)})
t1(n) ∈ O(g1(n)) t2(n) ∈ O(g2(n))
Then the following hold:
(we can throw away smaller summands)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Summarising Reasoning
with Big-Oh
28
Suppose
t1(n) + t2(n) ∈ O(max{g1(n), g2(n)})
t1(n) ∈ O(g1(n)) t2(n) ∈ O(g2(n))
Then the following hold:
c ⋅ t1(n) ∈ O(g1(n))
(we can throw away smaller summands)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Summarising Reasoning
with Big-Oh
28
Suppose
t1(n) + t2(n) ∈ O(max{g1(n), g2(n)})
t1(n) ∈ O(g1(n)) t2(n) ∈ O(g2(n))
Then the following hold:
c ⋅ t1(n) ∈ O(g1(n))
(we can throw away smaller summands)
(constants can be thrown away too)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Summarising Reasoning
with Big-Oh
28
Suppose
t1(n) + t2(n) ∈ O(max{g1(n), g2(n)})
t1(n) ∈ O(g1(n)) t2(n) ∈ O(g2(n))
Then the following hold:
c ⋅ t1(n) ∈ O(g1(n))
t1(n) ⋅ t2(n) ∈ O(g1(n) ⋅ g2(n))
(we can throw away smaller summands)
(constants can be thrown away too)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Summarising Reasoning
with Big-Oh
28
Suppose
t1(n) + t2(n) ∈ O(max{g1(n), g2(n)})
t1(n) ∈ O(g1(n)) t2(n) ∈ O(g2(n))
Then the following hold:
c ⋅ t1(n) ∈ O(g1(n))
t1(n) ⋅ t2(n) ∈ O(g1(n) ⋅ g2(n))
(we can throw away smaller summands)
(constants can be thrown away too)
(for nested loops: count number of times outer loop
is executed, multiply by cost of inner loop)
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Some Useful Formulas
29
From Stirling’s formula: n! ∈ O(nn+
1
2 )
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Some Useful Formulas
29
From Stirling’s formula: n! ∈ O(nn+
1
2 )
this is not the time complexity of an
algorithm to compute n-factorial
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Some Useful Formulas
29
From Stirling’s formula: n! ∈ O(nn+
1
2 )
this is not the time complexity of an
algorithm to compute n-factorial
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
Some Useful Formulas
29
From Stirling’s formula: n! ∈ O(nn+
1
2 )
this is not the time complexity of an
algorithm to compute n-factorial
See also Cormen’s Appendix A or Levitin’s Appendix A.
Levitin’s Appendix B is a tutorial on recurrence relations.
Copyright University of Melbourne 2016, provided under Creative Commons Attribution License
The Road Ahead
• You’ll get much more familiar with asymptotic
analysis as we use it on algorithms we meet in this
course.
• Next week we begin our study of algorithms by
looking at brute force approaches
30