Divide & Conquer Master Theorem
2021-01-12 CSC373 Winter 2021 – Sam Toueg 1
Divide & Conquer
• Divide & conquer algorithm:
Ø divide problem of size 𝑛 into 𝑎 smaller subproblems of size 𝑛/𝑏 each
Ø recursively solve each subproblem
Ø combine the subproblem solutions into the solution of the original problem
• Runtime 𝑛>1: 𝑇(𝑛)= 𝑎 · 𝑇(𝑛/𝑏)+ 𝑐·𝑛% integer𝑎≥1,𝑏>1,𝑐≥0,𝑑≥0
Time on input of size 𝑛
Assume that 𝑛 is a power of 𝑏
Time for the
recursive calls
Time for dividing the problem and combining the subproblem solutions
# Problems Size
1𝑛
𝒂 𝒂𝒂
……
𝒂
𝑎 𝑎&
𝑎!”#!$
= 𝑛!”#!’
𝑛/𝑏 𝑛/𝑏&
1= 𝑛/𝑏!”#!$ = 𝑛/𝑛 2
…
𝒂𝒂𝒂𝒂𝒂𝒂𝒂𝒂𝒂
………………
………
… … …
2021-01-12
CSC373 Winter 2021 – Sam Toueg
Master Theorem
• Divide & conquer algorithm:
Ø divide problem of size 𝑛 into 𝑎 smaller subproblems of size 𝑛/𝑏 each
Ø recursively solve each subproblem
Ø combine the subproblem solutions into the solution of the original problem
• Runtime 𝑛>1: 𝑇(𝑛)= 𝑎 · 𝑇(𝑛/𝑏)+ 𝑐·𝑛% integer𝑎≥1,𝑏>1,𝑐≥0,𝑑≥0 Time on input Time for the Time for dividing the problem and
of size 𝑛 recursive calls combining the subproblem solutions
𝑛=1: 𝑇(1)=𝑐
Master Theorem: See course handout for a proof!
special case 𝑑 = 1 𝑇(𝑛)= 𝑎 · 𝑇(𝑛/𝑏)+ 𝑐·𝑛
Θ 𝑛% ,
𝑇(𝑛)= Θ 𝑛%𝑙𝑜𝑔𝑛, Θ 𝑛!”#!’ ,
if 𝑎 < 𝑏% if𝑎=𝑏% if 𝑎>𝑏%
Θ 𝑛 , 𝑇(𝑛)=:Θ 𝑛𝑙𝑜𝑔𝑛,
Θ 𝑛!”#!’ ,
if 𝑎 < 𝑏 if𝑎=𝑏
if 𝑎>𝑏
Note 1: the running time does not depend on the constant 𝑐
Note 2: in many algorithms 𝑑 = 1 (dividing and combining takes linear time) 2021-01-12 CSC373 Winter 2021 – Sam Toueg 3
Master Theorem — Well-Known Examples Master Theorem: 𝑇(𝑛) = 𝑎 · 𝑇(𝑛/𝑏) + 𝑐 ·𝑛%
Θ 𝑛% ,
𝑇(𝑛)= Θ 𝑛%𝑙𝑜𝑔𝑛, Θ 𝑛!”#!’ ,
if 𝑎 < 𝑏% if𝑎=𝑏% if 𝑎 > 𝑏%
• Merge Sort — sorting array of size 𝑛
Ø Split array into two arrays of size 𝑛/2 each
Ø Sort each subarray (recursively)
Ø Merge the two sorted subarrays (takes linear time)
Ø𝑎=2,𝑏=2, 𝑑=1 ⇒𝑎=𝑏! so: 𝑇(𝑛)=Θ 𝑛𝑙𝑜𝑔𝑛
• Binary Search — search an item 𝑥 in a sorted array of size 𝑛
Ø Compare 𝑥 with middle element of the array; depending on outcome: Ø Return found, or recursively search first or second half of the array
Ø𝑎=1,𝑏=2, 𝑑=0⇒𝑎=𝑏! so:𝑇(𝑛)=Θ 𝑙𝑜𝑔𝑛
2021-01-12 CSC373 Winter 2021 – Sam Toueg 4
Divide & Conquer
Karatsuba’s integer multiplication
2021-01-12 CSC373 Winter 2021 – Sam Toueg 6
Overview and Motivation • Binarynumber:100111010….
• Add two binary numbers of length 𝑛 Ø Running Time: Θ(𝑛)
• Multiply two binary numbers of length 𝑛 Ø Running Time: Θ(𝑛#)
𝑥 𝑦
• Can we multiply two numbers in less than Θ(𝑛#) time complexity? • Kolmogorov conjectured (in 1956) that Θ(𝑛#) is the best possible!
2021-01-12 CSC373 Winter 2021 – Sam Toueg 7
Assume 𝑛 is a power of 2
𝑥
𝑛/2
𝑛/2
Divide & Conquer – Idea I
𝑥;
𝑥<
𝑦;
𝑦<
𝑦
𝑛
This is a D&C algorithm
𝑥 = 𝑥; ' 2=/> + 𝑥< 𝑦 = 𝑦; ' 2=/> + 𝑦<
𝑥 ' 𝑦 = 𝑥; ' 𝑦; ' 2= + (𝑥; ' 𝑦< + 𝑥< ' 𝑦;) ' 2=/> + 𝑥< ' 𝑦<
•𝑇𝑛 =4'𝑇 => +𝑐’𝑛 for𝑛>1;𝑇(1)=𝑐for𝑛=1 Ø Master Theorem: 𝑎 = 4, 𝑏 = 2, 𝑑 = 1
• Thisiscase(𝑐)oftheMasterTheorem(𝑎=4>𝑏; =2):
Ø𝑇 𝑛 =Θ 𝑛”#$!% =Θ 𝑛”#$”& =Θ 𝑛’
2021-01-12 CSC373 Winter 2021 – Sam Toueg computation! 8
We did not speed up the
Divide & Conquer – Idea II (Karatsubas 1962)
𝑥@𝑦=𝑥( @𝑦( @2$ +(𝑥( @𝑦) +𝑥) @𝑦()@2$/& +𝑥) @𝑦)
Idea: Rewrite the above expression to have 3 multiplications instead of 4 𝑥M𝑦=𝑥(M𝑦(M2)+(𝑥(+𝑥* M 𝑦(+𝑦* −𝑥(M𝑦(−𝑥*M𝑦*)M2)/’+𝑥*M𝑦*
• 𝑇 𝑛 = 3 C 𝑇 &# + 𝑐 C 𝑛
Ø Master Theorem: 𝑎 = 3, 𝑏 = 2, 𝑑 = 1
• Since𝑎=3>𝑏$ =2,thisiscase(𝑐)oftheMasterTheorem: Ø𝑇 𝑛 =Θ 𝑛!”#!$ =Θ 𝑛!”#”% =Θ 𝑛&.()(…
• Minorissue:acarrymayincreaselengthof𝑥$ +𝑥% and 𝑦$ +𝑦% to=> +1 1 𝑛/2
𝑢$
𝑢%
𝑥$ + 𝑥% 𝑦$ + 𝑦%
2021-01-12
= 𝑢$· 2&/# + 𝑢%
= 𝑣$· 2&/# + 𝑣%
𝑢$ ·𝑣$ ·2& +(𝑢$ ·𝑣% +𝑢% ·𝑣$)·2&/# +𝑢% ·𝑣%
𝑣$
𝑣%
1×1 1x$ $x1 $x$ &&&&
CSC373 Winter 2021 – Sam Toueg 9
𝑥@𝑦=𝑥( @𝑦( @2$ +( 𝑥( +𝑥) @ 𝑦( +𝑦) −𝑥( @𝑦( −𝑥) @𝑦))@2$& +𝑥) @𝑦)
MULT(𝑥,𝑦):
• 𝑛 ← max{𝑙𝑒𝑛𝑔𝑡h 𝑥 ,𝑙𝑒𝑛𝑔𝑡h 𝑦 }
𝑐
𝑢
𝑏𝑠𝑡𝑏𝑎𝑎
• Put 0’s to the left of the shortest of 𝑥 and 𝑦 so both have length 𝑛
𝑥 ;
𝑦;
𝑥 <
𝑦<
• 𝑥# ←leftmost𝑛/2bitsof𝑥
• 𝑦# ← leftmost 𝑛/2 bits of 𝑦
• 𝑥$ ← rightmost 𝑛/2 bits of 𝑥
• 𝑦$ ← rightmost 𝑛/2 bits of 𝑥
• 𝑠 ← 𝐴𝑑𝑑(𝑥$, 𝑥#)
• 𝑡 ← 𝐴𝑑𝑑(𝑦$, 𝑦#)
• 𝑎 ← 𝑀𝑢𝑙𝑡(𝑥$, 𝑦$)
• 𝑏 ← 𝑀𝑢𝑙𝑡(𝑥#, 𝑦#)
• 𝑐 ← 𝑀𝑢𝑙𝑡(𝑠, 𝑡)
• 𝑢 ← 𝑆𝑢𝑏𝑡𝑟𝑎𝑐𝑘(𝑐, 𝐴𝑑𝑑(𝑎, 𝑏))
• Put𝑛zerostotherightof𝑏
• Put 𝑛/2 zeros to the right of 𝑢
• Return 𝐴𝑑𝑑(𝑏, 𝐴𝑑𝑑 (𝑢 , 𝑎)) 2021-01-12
𝑥 𝑦
1
0
0
1
0
1
1
1
0
0
0
1
1
0
1
0
CSC373 Winter 2021 - Sam Toueg
10
Integer Multiplication
• Whatcanwedowhen𝑛isnotapowerof2?
• Embed each vector in a vector whose dimension is the next power of 2
• In the worst-case, this doubles the dimension:
Ø from 𝑛+,-". we go to at most (2𝑛)+,-".
Ø Since 2+,-". = 3 this increases the time complexity by a factor of at most 3
Example:
35
𝑥
𝑦 6
000
00
2
2021-01-12
CSC373 Winter 2021 - Sam Toueg 11
Integer Multiplication
• Can one multiply two 𝑛 -digits integers in less than Θ 𝑛KLM+N time?
• 1962: Karatsuba Θ 𝑛KLM+N ≈ Θ 𝑛;.PQP...
• 1971: Schönhage-Strassen Θ 𝑛 ' 𝑙𝑜𝑔 𝑛 ' 𝑙𝑜𝑔𝑙𝑜𝑔 𝑛
• 2019: Harvey and van der Hoeven Θ 𝑛 ' 𝑙𝑜𝑔 𝑛 !!
• https://rjlipton.wordpress.com/2019/03/29/integer-multiplication-in-nlogn-time/
2021-01-12 CSC373 Winter 2021 - Sam Toueg 12
Divide & Conquer
Strassen's Matrix Multiplication Algorithm
2021-01-12 CSC373 Winter 2021 - Sam Toueg 13
Overview and Motivation • Let 𝐴 and 𝐵 be two 𝑛×𝑛 matrices
ØAssume 𝑛 is a power of 2 •Wewanttocompute𝐶= 𝐴·𝐵
Ø Running Time: Θ(𝑛N)
• Can we multiply two 𝑛×𝑛 matrices in less than
Θ(𝑛Q) time?
2021-01-12 CSC373 Winter 2021 - Sam Toueg 14
Divide & Conquer – Idea I
𝑛/2 𝐴𝑛/2 𝑛/2 𝐵𝑛/2 𝑛×
𝑏;
𝑏>
𝑏N
𝑏T
𝑐;
𝑐>
𝑐N
𝑐T
𝑎;
𝑎>
𝑎N
𝑎T
𝑛/2 𝑛/2
𝑛/2 𝐶𝑛/2 𝑛𝑛𝑛
=
𝑐( = 𝑎( @ 𝑏( + 𝑎& @ 𝑏. 𝑐& = 𝑎( @ 𝑏& + 𝑎& @ 𝑏/ 𝑐. = 𝑎. @ 𝑏( + 𝑎/ @ 𝑏. 𝑐/ = 𝑎. @ 𝑏& + 𝑎/ @ 𝑏/
•𝑇𝑛 =8’𝑇 => +𝑐’𝑛> for𝑛>1;𝑇(1)=𝑐for𝑛=1 Ø Master Theorem: 𝑎 = 8, 𝑏 = 2, 𝑑 = 2
• Thisiscase(𝑐)oftheMasterTheorem(𝑎=8>𝑏S =4): Ø𝑇 𝑛 =Θ 𝑛”#$!% =Θ 𝑛”#$”, =Θ 𝑛- Wedidnotspeed
up the
2021-01-12 CSC373 Winter 2021 – Sam Toueg computation! 15
𝑐( = 𝑎( @ 𝑏( + 𝑎& @ 𝑏.
Divide & Conquer – Idea II (Strassen)
Idea: Compute 𝑐;, 𝑐>, 𝑐N, 𝑐T with 7 ()’ x )’ ) matrix multiplications, not 8
𝑐( = 𝑎( @ 𝑏( + 𝑎& @ 𝑏. 𝑐& = 𝑎( @ 𝑏& + 𝑎& @ 𝑏/ 𝑐. = 𝑎. @ 𝑏( + 𝑎/ @ 𝑏. 𝑐/ = 𝑎. @ 𝑏& + 𝑎/ @ 𝑏/
• 𝑚( = (𝑎’ − 𝑎&) M (𝑏- + 𝑏&) • 𝑚’ = (𝑎( + 𝑎&) M (𝑏( + 𝑏&) • 𝑚- = (𝑎( − 𝑎-) M (𝑏( + 𝑏’) • 𝑚& = (𝑎( + 𝑎’) M 𝑏&
• 𝑚. = 𝑎( M (𝑏’ − 𝑏&) • 𝑚/ = 𝑎& M (𝑏- − 𝑏() • 𝑚0 = (𝑎-+𝑎&) M 𝑏(
instead of computing 𝑐#, 𝑐%, 𝑐&, 𝑐’ like this…
• 𝑐( = 𝑚( + 𝑚’ − 𝑚& + 𝑚/
• 𝑇 𝑛 = 7 M 𝑇 )’ + 𝑐 M 𝑛 ‘
Ø Master Theorem: 𝑎 = 7, 𝑏 = 2, 𝑑 = 2
• Thisiscase(𝑐)oftheMasterTheorem(𝑎=7>𝑏! =4): Ø𝑇 𝑛 =Θ 𝑛!”#!’ =Θ 𝑛!”#”0 =Θ 𝑛&.2(
• 𝑐’ = 𝑚& + 𝑚.
• 𝑐- = 𝑚/ + 𝑚0
• 𝑐& = 𝑚’ − 𝑚- + 𝑚. + 𝑚0
Check it at home (when boredJ)
2021-01-12 CSC373 Winter 2021 – Sam Toueg
16
Divide & Conquer – Idea II (Strassen)
• Whatcanwedowhen𝑛isnotapowerof2?
• Embed each matrix in a matrix whose dimension is the next power of 2
• In the worst-case, this doubles the dimension:
Ø From 𝑛+,-“0 we go to at most (2𝑛)+,-“0
Ø Since 2+,-“0 = 7 this increases the time complexity by a factor of at most 7
Example: 𝑛 = 155 155
101
155 101 155 + 101 = 256 = 22
𝐴
0
0
0
2021-01-12
CSC373 Winter 2021 – Sam Toueg 17