COMP2100/COMP6442
Algorithms Part II
– Lecture 6]
Kin Chau [
Sid Chi
1
Recap from Last Lecture
• Divide-and-conquer
• Example: Merge Sort, Karatsuba Integer Multiplication
• How did we measure the speed of an algorithm?
• Count the number of operations
• How the number scales with respect to the input size • Time complexity of computation
• Karatsuba multiplication scales as n1.6
2
Goals of This Lecture
• Let us formally formulate the time complexity of computation • How to formally measure the running time of an algorithm?
• Big-O, Big-Ω, Big-Θ notations
• General approach of the running time with recursive algorithms • The Master theorem
3
Big
• What do we mean when we measure runtime?
• How long does it take to solve the problem, in seconds or minutes or hours?
• The exact runtime is heavily dependent on the programming language, system architecture, etc.
• But the most factor is the input size (e.g. the number of bits that used in encoding input)
• We want a way to talk about the running time of an algorithm, with respect to the input size
–
O notation
4
Main idea
• Focus on how the runtime scales with n (the input size)
5
Asymptotic Analysis
• How does the running time scale as n gets large?
• One algorithm is “faster” than another if its runtime scales better
with the size of the input
• Pros
• Abstracts away from hardware- and language-specific issues • Makes algorithm analysis much more tractable
• Cons
• Only makes sense if n is large (compared to the constant factors)
• 2100000000000000 n
• is “better” than n2 ?!?!
6
Big
• Big-O means an upper bound
• Let T(n), g(n) be functions of positive integers
• Think of T(n) as the running time: positive and increasing in n
• We say that “T(n) = O(g(n))” if g(n) grows at least as fast as T(n), when
n gets large • Formally,
–
O
T(n) = O(g(n))
There exist c, n0 > 0, such that 0 T(n) c g(n),
for all n n0
7
Example
•2n2 +10=O(n2)
T(n) = O(g(n))
There exist c, n0 > 0, such that 0 T(n) c g(n),
for all n n0
•Choosec=3,n0 =4
• Then 0 2n2 + 10 3n2, for all n 4
8
Example
•2n2 +10=O(n2)
T(n) = O(g(n))
There exist c, n0 > 0, such that 0 T(n) c g(n),
for all n n0
•Choosec=7,n0 =2
• Then 0 2n2 + 10 7n2, for all n 2
9
Example
• n = O(n2)
T(n) = O(g(n))
There exist c, n0 > 0, such that 0 T(n) c g(n),
for all n n0
•Choosec=1,n0 =1
• Then 0 n n2, for all n 1
10
Big
• Big-Ω means an lower bound
• Let T(n), g(n) be functions of positive integers
• Think of T(n) as the running time: positive and increasing in n
• We say that “T(n) = Ω(g(n))” if g(n) grows at most as fast as T(n), when
n gets large • Formally,
–
Ω
T(n) = Ω(g(n))
There exist c, n0 > 0, such that c g(n) T(n),
for all n n0
11
Big
• Big-Θ means a tight bound
• Let T(n), g(n) be functions of positive integers
• Think of T(n) as the running time: positive and increasing in n
• We say that “T(n) = Θ(g(n))” if g(n) grows tightly as fast as T(n), when
n gets large • Formally,
–
Θ
T(n) = Θ(g(n))
There exist c, c’, n0 > 0, such that c g(n) T(n) c’ g(n),
for all n n0
12
Example
• 2n2 + 10 = O(n2), 2n2 + 10 = Ω(n2), 2n2 + 10 = Θ(n2) • 2n + 10 = O(n2), 2n + 10 Ω(n2), 2n + 10 Θ(n2)
• 2n2 + 10 O(n), 2n2 + 10 = Ω(n), 2n2 + 10 Θ(n)
• Note that if T(n) = O(g(n)) and T(n) = Ω(g(n)), then T(n) = Θ(g(n)) • Why?
13
Example 1
• What is the running time T(n) of the following procedure? • Assume c() requires constant running time
• T(n) = O(n4)
public void method(int n) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) { for (int k = 0; k < n; k++) {
for (int l = 0; l < n; l++) { c();
} }
} }
14
Example 2
• What is the running time T(n) of the following procedure? • Assume c() requires constant running time
• h = 1, 2, 4, ..., 2log(n) • T(n) = O(log n)
public void method(int n) { h=1;
}
while (h <= n)
{
c();
h = 2*h; }
15
Example 3
• What is the running time T(n) of the following procedure? • Assume c() requires constant running time
• Each inner for-loop (i) gets j times • T(n) = 1+2+...+n = O(n2)
public void method(int n) {
for (int j = 0; j < n; j++) {
for (int i = 0; i < j; i++) {
c();
} }
}
16
Summing Up
• Big-O
• T(n) = O(g(n)) there exist c, n0 > 0, such that 0 T(n) c g(n), for all n n0
• Big-Ω
• T(n) = Ω(g(n)) there exist c, n0 > 0, such that c g(n) T(n), for all n n0
• Big-Θ
• T(n) = Θ(g(n)) there exist c, c’, n0 > 0, such that c g(n) T(n) c’ g(n), for
all n n0
• But we should always be careful not to abuse it
• c =21000000
• n ≥ n =21000000
0 17
Exercise
• Suppose the n is the size of input. Which of the following algorithms are the fastest and slowest?
A. Algorithm A with runtime modelled as T(n) = 1.5n + n
B. Algorithm B with runtime modelled as T(n) = 2n + 200000 C. Algorithm C with runtime modelled as T(n) = n1.1
• Which one of the following is INCORRECT?
A. 2n2 + 1000010000 is in O(2n2)
B. 2n2 + n + 100 is in O(n3)
C. 0.1n2 is in O(n log(n))
D. 2n2 + 10 is in O(n2)
18
The Master Theorem
• Recursive integer multiplication • T(n) = 4 T(n/2) + O(n)
• T(n) = O(n2)
• Karatsuba integer multiplication • T(n) = 3 T(n/2) + O(n)
• T(n) = O(nlog(3)) O(n1.6)
• What’s the pattern?
• A formula that solves recurrences when all of sub-problems are the same size • “Generalized” tree method
19
The Master Theorem
• The master theorem applies to recurrence form: T(n) = aT(n/b) + O(nd),
where a 1, b > 1
• a: number of subproblems
• b: factor by which input size shrinks
• d: need to do nd work to create all the subproblems and combine their solutions
• Case 1: If a = bd, then T(n) = O(nd log(n)) • Case 2: If a < bd, thenT(n) = O(nd)
• Case 3: If a > bd, then T(n) = O(nlogb(a))
20
Example
• T(n) = T(n/2) + O(1)
• a = 1, b = 2, d = 0 a = bd • Hence, T(n) = O(log(n))
• T(n) = 2T(n/2) + O(1)
• a = 2, b = 2, d = 0 a > bd • Hence, T(n) = O(n)
• T(n) = T(n/2) + O(n)
• a = 1, b = 2, d = 1 a < bd • Hence, T(n) = O(n)
• T(n) = 2T(n/2) + O(n)
• a = 2, b = 2, d = 1 a = bd • Hence, T(n) = O(n log(n))
21
Example
• T(n) = 4T(n/2) + O(1)
• a = 4, b = 2, d = 0 a > bd • Hence, T(n) = O(n2)
• T(n) = 3T(n/2) + O(1)
• a = 3, b = 2, d = 0 a > bd
• Hence, T(n) = O(nlog(3)) O(n1.6)
• T(n) = 4T(n/2) + O(n)
• a = 4, b = 2, d = 1 a > bd • Hence, T(n) = O(n2)
• T(n) = 3T(n/2) + O(n)
• a = 3, b = 2, d = 1 a > bd
• Hence, T(n) = O(nlog(3)) O(n1.6)
• (Karatsuba Multiplication) 22
Example 4
• What is the running time T(n) of the following procedure?
• If n > 0,
• T(n) = T(n – 1) + 1
• Else
• T(n) = 1
• Hence, T(n) = O(n)
public void method(int n) { c();
}
if (n > 0) method(n-1);
23
Example 5
• What is the running time T(n) of the following procedure?
• If n > 0,
• T(n) = T(n/2) + 1
• Else
• T(n) = 1
• Hence, T(n) = O(log(n))
public void method(int n) { c();
}
if (n > 0) method(n/2);
24
Example 6
• What is the running time T(n) of the following procedure?
• If n > 0,
• T(n) = 2T(n/2) + 1
• Else
• T(n) = 1
• Hence, T(n) = O(n)
public void method(int n) { c();
}
if (n > 0) { method(n/2); method(n/2);}
25
Proof of the Master Theorem
• We’ll do the same recursion tree thing we did for multiplication, but be more careful.
• Suppose that T(n) = aT(n/b) + cnd
• The hypothesis of the Master Theorem was the extra work at each
level was O(nd)
• That’s NOT the same as work cnd for some constant c
• That’s true … we’ll actually prove a weaker statement that uses this hypothesis instead of the hypothesis that T(n) = aT(n/b) + O(nd)
26
T(n) = aT(n/b) + cnd 1 problem of size n
a problems of size n/b a2 problems of size n/b2
…………
at problems of size n/bt …………
Level
# Problems
Size of each problem
Amount of work at this level
0
1
n
cnd
1
a
n/b
ac(n/b)d
2
a2
n/b2
a2c(n/b2)d
……
……
……
……
t
at
n/bt
atc(n/bt)d
……
……
……
……
logb(n)
alogb(n)
1
alogb(n) c
alogb(n) problems of size 1
27
Level
# Problems
Size of each problem
Amount of work at this level
0
1
n
cnd ac(n/b)d a2c(n/b2)d …… atc(n/bt)d
…… alogb(n) c
1
a
n/b
2
a2
n/b2
……
……
……
t
at
n/bt
……
……
……
logb(n)
alogb(n)
1
Total Work = 𝑐 ⋅ 𝑛𝑑 ⋅
𝑡 𝑡=0 𝑏𝑑
σlog𝑏(𝑛) 𝑎
28
The Master Theorem
• The master theorem applies to recurrence form: T(n) = aT(n/b) + O(nd),
where a 1, b > 1
• a: number of subproblems
• b: factor by which input size shrinks
• d: need to do nd work to create all the subproblems and combine their solution
• Case 1: If a = bd, then T(n) = O(nd log(n)) • Case 2: If a < bd, thenT(n) = O(nd)
• Case 3: If a > bd, then T(n) = O(nlogb(a))
29
Closer Look at All the Cases
• Total Work = 𝑐 ⋅ 𝑛𝑑 ⋅ σlog𝑏(𝑛) 𝑎 𝑡, 𝑡=0 𝑏𝑑
• where σlog𝑏(𝑛) 𝑎 𝑡 is a sum of geometric sequence 𝑡=0 𝑏𝑑
•If𝑎 𝑏𝑑
•If𝑎 𝑏𝑑
•If𝑎 𝑏𝑑
𝑎 𝑡= O(nd log(n))
𝑎 𝑡= O(nd)
= 1, then T(n) = 𝑐 ⋅ 𝑛𝑑 ⋅ σlog𝑏(𝑛)
𝑡=0 𝑏𝑑
< 1, then T(n) = 𝑐 ⋅ 𝑛𝑑 ⋅ σlog𝑏(𝑛)
𝑡=0 𝑏𝑑
𝑎 𝑡= O(nlogb(a)) 𝑡=0 𝑏𝑑
> 1, then T(n) = 𝑐 ⋅ 𝑛𝑑 ⋅ σlog𝑏(𝑛)
30
The Eternal Struggle
• Branching causes the number of problems to explode! • The most work is at the bottom of the tree!
• The problems lower in the tree are smaller! • The most work is at the top of the tree!
31
Consider Three Different Cases
(Case 1) T(n) = 2T(n/2) + O(n) • a = 2, b = 2, d = 1 a = bd
(Case 2) T(n) = T(n/2) + O(n)
• a = 1, b = 2, d = 1 a < bd
(Case 3) T(n) = 4T(n/2) + O(n) • a = 4, b = 2, d = 1 a > bd
32
Consider Three Different Cases
(Case 1) T(n) = 2T(n/2) + O(n) • a = 2, b = 2, d = 1 a = bd
• The branching just balances out the amount of work
• The same amount of work is done at every level
• T(n) = (number of levels)(work per level) = log(n) O(n) = O(n log(n))
1 problem of size n
2 problems of size n/2
4 problems of size n/4 …………
at problems of size n/at …………
n problems of size 1
33
Consider Three Different Cases
(Case 2) T(n) = T(n/2) + O(n)
• a = 1, b = 2, d = 1 a < bd
• The amount of work done at the top (the biggest problem) swamps the amount of work done anywhere else
• T(n) = T(work at top) = O(n)
1 problem of size n 1 problems of size n/2
1 problems of size n/4 ............
1 problems of size n/2t ............
1 problems of size 1
34
Consider Three Different Cases
(Case 3) T(n) = 4T(n/2) + O(n) • a = 4, b = 2, d = 1 a > bd
• There are a HUGE number of leaves, and the total work is dominated by the time to do work at these leaves
• T(n) = O(work at bottom) = O( 4depth of tree ) = O(n2)
1 problem of size n 4 problems of size n/2
42 problems of size n/4 …………
4t problems of size n/2t …………
4depth of tree problems of size 1
35
Exercise
• Which of the following are the fastest and the slowest?
A. T(n) = T(n/2) + O(1)
B. T(n) = 5 T(n/6) + O(n)
C. T(n) = 2 T(n/3) + O(1)
D. T(n) = 10 T(n/30) + O(n1.1)
E. T(n) = T(0.5n) + O(n2)
F. T(n) = T(n-1) + T(n-2) + O(1)
36
Summary
• Asymptotic Analysis: Big-O, Big-Ω, Big-Θ • The ”Master Theorem” is a powerful tool
• It is a systematic approach to calculate general recurrence relations from scratch
• The master theorem applies to recurrence form: T(n) = aT(n/b) + O(nd),
where a 1, b > 1
• a: number of subproblems
• b: factor by which input size shrinks
• d: need to do nd work to create all the subproblems and combine their solution
• Case 1: If a = bd, then T(n) = O(nd log(n))
• Case 2: If a < bd, thenT(n) = O(nd)
• Case 3: If a > bd, then T(n) = O(nlogb(a))
37
38