Lecture3: Divide-and-

Conquer
DR VICTOR ODUMUYIWA
Learning Outcomes
At the end of this class, you should be able to:
 Demonstrate a good understanding of divide-and-
conquer algorithms
 Determine the running time of a recursive algorithm
 Solve recurrences
Readings
Chapter 2 and 4
◦ Cormen T.H., Leiserson C.E., Rivest R.L., & Stein C. (2009), Introduction to
Algorithms, MIT press.
Chapter 5
◦ Jon Kleinberg & Éva Tardos (2005) Algorithm Design, Pearson-Adisson Wesley
Divide-and-Conquer
 Many useful algorithms are recursive in nature
 Recursion is a way of resolving a problem by reducing it
to a smaller problem that looks like the initial problem
 In loose terms:
 If the given instance of the problem is simple or small enough, just
solve it
 Otherwise reduce it to one or more simpler instances of the same
problem
Recursion
 Generally expressed in terms of recurrences
 Running time of a recursive algorithm is described by a
recurrence equation
 Recurrence equation describes the overall running time of a problem of size
n in terms of the running time on smaller inputs
 T(n)=4T(n/2)+n
Using Divide-and-Conquer
Divide-and-conquer
 Divide: Break up the problem into a number of subproblems that are smaller instances of the
same problem
 Conquer: Solve the sub-problems recursively.
 Combine: combine the solutions to the sub-problems into overall solution for the original
problem.
Most common usage
 Break up problem of size n into two equal parts of size ½n.
 Solve two parts recursively.
 Combine two solutions into overall solution in linear time.
Consequence
 Brute force: n2.
 Divide-and-conquer: n log n.
Forms of Recurrences (1/2)
 Recurrences can take many forms

 A recursive algorithm might divide sub-problems into unequal

size such as 2/3 to 1/3 split

 If the divide and conquer takes linear time,

2𝑛 𝑛
 𝑇 𝑛 =𝑇 +𝑇 + Ꝋ(𝑛)
3 3
Forms of Recurrences (2/2)
 Subproblems are not necessarily constrained to being a constant
fraction of the original problem size

 For example, a recursive algorithm for computing the factorial of n

would create just one subproblem containing only one element fewer
than the original subproblem

 Each recursive call takes constant time plus the time for the
recurrence call it makes.
 𝑇 𝑛 = 𝑇 𝑛 − 1 + Ꝋ(1)
Merge-Sort (A, p, r)
The merge sort algorithm closely follows the divide-and-conquer paradigm.
 Divide: Divide the n-element sequence to be sorted into two sub-sequences of
n/2 elements each.
 Conquer: Sort the two sub-sequences recursively using merge sort.
 Combine: Merge the two sorted sub-sequences to produce the sorted answer.

1. If 𝑝 < 𝑟
2. q = (𝑝 + 𝑟)/2
3. MERGE-SORT(𝐴, 𝑝, 𝑞)
4. MERGE-SORT(𝐴, 𝑞 + 1, 𝑟)
5. MERGE(𝐴, 𝑝, 𝑞, 𝑟)
Jon von Neumann (1945)
Merge-sort

A L G O R I T H M S

A L G O R I T H M S divide O(1)

A G L O R H I M S T sort 2T(n/2)

A G H I L M O R S T merge O(n)

10
Merge(A,p,q,r))
1. n1 = q-p+1
2. n2 = r-q
3. Let L[1 .. n1 + 1] and R[1 .. n2 + 1] be new arrays
4. For i= 1 to n1
5. L[i] = A[p + i - 1]
6. for j = 1 to n2
7. R[j] = A[q + j]
8. L[n1 + 1] = ∞
9. R[n2 + 1] = ∞
10. i= 1
11. j=1
12. for k = p to r
13. if L[i] ≤ R[j]
14. A[k] = L[i]
15. i=i+1
16. else A[k] = R[j]
17. j=j +1
 Merge(A, p, q, r) Cost Times
1 n1 = q-p+1 c1 1
2 n2 = r-q c2 1
3 Let L[1 .. n1 + 1] and R[1 .. n2 + 1] c3 1
4 for i= 1 to n1 c4 n
5 L[i] = A[p + i - 1] c5 n-1
6 for j = 1 to n2 c6 n
7 R[j] = A[q + j] c7 n-1
8 L[n1 + 1] = ∞ c8 1
9 R[n2 + 1] = ∞ c9 1
10 i= 1 c10 1
11 j=1 c11 1
12 for k = p to r c12 n
13 if L[i] ≤ R[j] c13 n-1
14 A[k] = L[i] c14 n-1
15 i=i+1 c15 n-1
16 else A[k] = R[j] c16 n-1
17 j=j +1 c17 n-1
Proof by Recursion Tree
 0 if n  1

T(n)   2T (n / 2)  n otherwise

 sorting both halves merging
T(n) n

 T(n/2) T(n/2) 2(n/2)

T(n/4) T(n/4) T(n/4) T(n/4) 4(n/4)

log2n
...
T(n / 2k) 2k (n / 2k)

...

T(2) T(2) T(2) T(2) T(2) T(2) T(2) T(2) n/2 (2)

n log2n
14
Solving Recurrences
 Substitution method
 Recursion tree method
 Master method
Recursion Tree Method(1)
𝑐, 𝑛=1
𝑇 𝑛 =ቐ 𝑛
2𝑇 + 𝑐, 𝑛>1
2

T(n)

T(n/2) T(n/2)

T(n/4) T(n/4) T(n/4) T(n/4)

 Recursion Tree Method(2)
T(n) c

T(n/2) T(n/2) c c

T(n/4) T(n/4) T(n/4) T(n/4) c c c c

T(n / 2k) T(n / 2k)

T(1) T(1) T(1) T(1) T(1) T(1) T(1) T(1) c c c c c c c c

𝑇 𝑛/𝑛) = 𝑇(1
Recursion Tree Method(3)
𝑇 𝑛 = 𝑐 + 2𝑐 + 4𝑐 + ⋯ + 𝑛𝑐
𝑇 𝑛 = 𝑐(1 + 2 + 4 + ⋯ + 𝑛)
Assume n = 2k
𝑇 𝑛 = 𝑐(1 + 2 + 4 + ⋯ + 2𝑘)
𝑇 𝑛 = 𝑐(20 + 21 + 22 + ⋯ + 2𝑘)
𝑎(𝑟 𝑛 − 1)
Using geometric progression (n = k+1)
(2𝑘+1 − 1) 𝑟−1
𝑇 𝑛 =𝑐
(2 − 1)
𝑇 𝑛 = 𝑐 2𝑘+1 − 1
𝑇 𝑛 = 𝑐(2𝑘 𝑥 21 − 1) = 𝑐 𝑛 𝑥 21 − 1 = 𝑐(2𝑛 − 1)
𝑇 𝑛 = 𝑂(𝑛)
Recursion Tree Method(4)
1, 𝑛=1
𝑇 𝑛 =ቐ 𝑛
2𝑇 + 𝑛, 𝑛>1
2

T(n)

𝑛 𝑛 𝑛
T(n/2) T(n/2) 𝑇 = 2𝑇 +
2 4 2
𝑛 𝑛 𝑛
T(n/4) T(n/4) T(n/4) T(n/4) 𝑇 = 2𝑇 +
4 8 4
 Recursion Tree Method(5)
T(n) n

T(n/2) T(n/2) n/2 n/2

T(n/4) T(n/4) T(n/4) T(n/4) n/4 n/4 n/4 n/4

T(n / 2k) T(n / 2k)

T(1) T(1) T(1) T(1) T(1) T(1) T(1) T(1) 1 1 1 1 1 1 1 1

𝑇 𝑛/𝑛) = 𝑇(1
Recursion Tree Method(6)
Workdone
n n

n/2 n/2 n

n/4 n/4 n/4 n/4 n

T(n / 2k)

1 1 1 1 1 1 1 1 n
Recursion Tree Method(7)
𝑇 𝑛 = 𝑛 𝑥 𝑡𝑜𝑡𝑎𝑙 𝑛𝑢𝑚𝑏𝑒𝑟 𝑜𝑓 𝑙𝑒𝑣𝑒𝑙𝑠 𝑖𝑛 𝑡ℎ𝑒 𝑟𝑒𝑐𝑢𝑟𝑠𝑖𝑜𝑛 𝑡𝑟𝑒𝑒
𝐻𝑜𝑤 𝑚𝑎𝑛𝑦 𝑙𝑒𝑣𝑒𝑙𝑠 𝑎𝑟𝑒 𝑖𝑛 𝑡ℎ𝑒 𝑟𝑒𝑐𝑢𝑟𝑠𝑖𝑜𝑛 𝑡𝑟𝑒𝑒?
𝑛 𝑛 𝑛 𝑛 𝑛
0
, 1 , 2 , 3 ,,, 𝑘
2 2 2 2 2
we have 𝒌 + 𝟏 𝑙𝑒𝑣𝑒𝑙𝑠
Assume 𝑛 = 2𝑘
log 2 𝑛 = log 2 2𝑘
𝑘 = log 2 𝑛
Since we have 𝒌 + 𝟏 levels,
Total number of levels in the reursion tree = log 𝑛 + 1
𝑇 𝑛 = 𝑛(log 𝑛 + 1)
𝑇 𝑛 = 𝑂(𝑛𝑙𝑜𝑔 𝑛)
Solving Recurrences – Back Substitution (1)
A(n) 1, 𝑛=1
𝑇 𝑛 =ቊ
{ if (n>1) return A(n-1)} 1 + 𝑇(𝑛 − 1), 𝑛>1

𝑇 𝑛 = 1 + 𝑇(𝑛 − 1) −−−−−−−−−−−−−−−−−−−−−−− −(1)

𝑇 𝑛 − 1 = 1 + 𝑇 𝑛 − 2 −−−−−−−−−−−−−−−−−−−−− − 2
𝑇 𝑛 − 2 = 1 + 𝑇 𝑛 − 3 −−−−−−−−−−−−−−−−−−−−− −(3)
Substitute (3) into (2)

𝑇 𝑛 − 1 = 1 + 1 + 𝑇 𝑛 − 3 −−−−−−−−−−−−−−−−−−− −(4)
Solving Recurrences – Back Substitution (2)
Substitute (4) into (1)

𝑇 𝑛 = 1 + 1 + 1 + 𝑇(𝑛 − 3) −−−−−−−−−−−−−−−−−−− −(5)

𝑇 𝑛 = 3 + 𝑇 𝑛 − 3 −−−−−−−−−−−−−−−−−−−−−−−− −(6)
.
.
.

𝑇 𝑛 = 𝑘 + 𝑇(𝑛 − 𝑘) −−−−−−−−−−−−−−−−−−− −(7)

 Solving Recurrences – Back Substitution (3)
𝑇 𝑛 = 𝑘 + 𝑇(𝑛 − 𝑘) −−−−−−−−−−−−−−−−−−− −(7)

𝑊ℎ𝑒𝑛 𝑘 = 𝑛 − 1, 𝑡ℎ𝑒𝑛 𝑡ℎ𝑒 𝑟𝑒𝑐𝑢𝑟𝑟𝑒𝑛𝑐𝑒 𝑏𝑜𝑡𝑡𝑜𝑚𝑠 𝑜𝑢𝑡 (𝑖. 𝑒. 𝑟𝑒𝑎𝑐ℎ𝑒𝑠 𝑡ℎ𝑒 𝑏𝑎𝑠𝑒 𝑐𝑜𝑛𝑑𝑖𝑡𝑖𝑜𝑛)

𝑇 𝑛 =𝑛−1+𝑇 𝑛− 𝑛−1
𝑇 𝑛 =𝑛−1+𝑇 𝑛−𝑛+1
𝑇 𝑛 =𝑛−1+𝑇 1
𝑇 𝑛 =𝑛−1+1
𝑇 𝑛 =𝑛
𝑇 𝑛 = 𝑂(𝑛)
Solving Recurrences – Back Substitution (4)
1, 𝑛=1
𝑇 𝑛 =ቊ
𝑛 + 𝑇(𝑛 − 1), 𝑛>1

𝑇 𝑛 = 𝑛 + 𝑇(𝑛 − 1) −−−−−−−−−−−−−−−−−−−−−−−−−−− −(1)

𝑇 𝑛 − 1 = (𝑛 − 1) + 𝑇 𝑛 − 2 −−−−−−−−−−−−−−−−−−−−− − 2
𝑇 𝑛 − 2 = (𝑛 − 2) + 𝑇 𝑛 − 3 −−−−−−−−−−−−−−−−−−−−− −(3)

Substitute (3) into (2)

𝑇 𝑛 − 1 = (𝑛 − 1) + (𝑛 − 2) + 𝑇 𝑛 − 3 −−−−−−−−−−−−−−− −(4)
Solving Recurrences – Back Substitution (5)
Substitute (4) into (1)

𝑇 𝑛 = 𝑛 + 𝑛 − 1 + 𝑛 − 2 + 𝑇 𝑛 − 3 −−−−−−−−−−−−−− −(5)
.
.
.
𝑇 𝑛 = 𝑛 + 𝑛 −1 + 𝑛 −2 +⋯+ 𝑛 − 𝑘 + 𝑇 𝑛 − 𝑘 + 1 −− −(6)
Solving Recurrences – Back Substitution (6)
𝑇 𝑛 = 𝑛 + 𝑛 −1 + 𝑛 −2 +⋯+ 𝑛 − 𝑘 + 𝑇 𝑛 − 𝑘 + 1 −− −(6)

What value of k will turn T n − k + 1 to T(1) ?

𝑊ℎ𝑒𝑛 𝑘 = 𝑛 − 2, 𝑡ℎ𝑒 𝑟𝑒𝑐𝑢𝑟𝑟𝑒𝑛𝑐𝑒 𝑏𝑜𝑡𝑡𝑜𝑚𝑠 𝑜𝑢𝑡

𝑇 𝑛 = 𝑛 + 𝑛 − 1 + 𝑛 − 2 + ⋯ + 𝑛 − (𝑛 − 2) + 𝑇 𝑛 − (𝑛 − 2) + 1
𝑇 𝑛 = 𝑛 + 𝑛 − 1 + 𝑛 − 2 + ⋯ + 2 +1
𝑛(𝑛 + 1)
𝑇 𝑛 =
2
𝑇 𝑛 = 𝑂(𝑛2)
Master Method
Let a ≥ 1 and b > 1 be constants. Let f(n) be a function, and let T(n) be defined on the non-
negative integers by the recurrence
𝑛
𝑇 𝑛 =𝑎𝑇 + 𝑓(𝑛)
𝑏

Where we interpret 𝑛/𝑏 𝑜𝑟 𝑛/𝑏 . Then T(n) has the following asymptotic bounds:
1. If 𝑓 𝑛 = 𝑂(𝑛log𝑏 𝑎−ꞓ) for some constant ꞓ > 0, then 𝑇 𝑛 = Ꝋ(𝑛log𝑏𝑎 )
2. If 𝑓 𝑛 = Ꝋ(𝑛log𝑏 𝑎 ), then 𝑇 𝑛 = Ꝋ(𝑛log𝑏𝑎 lg 𝑛)
𝑛
3. If 𝑓 𝑛 = ꭥ(𝑛log𝑏 𝑎+ꞓ ) for some constant ꞓ > 0, and if 𝑎𝑓 ≤ 𝑐𝑓(𝑛) for some constant c < 1
𝑏
and all sufficiently large n, then 𝑇 𝑛 = Ꝋ(𝑓(𝑛)).
Solving Recurrences using Master Method
𝑛
Solve this recurrence: 𝑇 𝑛 =9𝑇 +𝑛
3
Solution
𝑎 = 9, 𝑏 = 3, 𝑓 𝑛 = 𝑛 , and 𝑛log𝑏𝑎 = 𝑛log39 = Ꝋ(𝑛2)
Since 𝑓 𝑛 = 𝑂(𝑛log39−𝜀 ) where 𝜀 = 1, case 1 can be applied
𝑇 𝑛 = Ꝋ(𝑛log3 9 ) = Ꝋ(𝑛2 )
Solving Recurrences using Master Method
𝑛
Solve this recurrence: 𝑇 𝑛 =2𝑇 + 𝑛𝑙𝑜𝑔 𝑛
2
Solution
𝑎 = 2, 𝑏 = 2, 𝑓 𝑛 = 𝑛𝑙𝑜𝑔𝑛
Using formula 2,
𝑓 𝑛 = Ꝋ(𝑛log𝑏𝑎 𝑙𝑜𝑔𝑘𝑛) => Ꝋ(𝑛log22 𝑙𝑜𝑔1𝑛) =𝑛𝑙𝑜𝑔𝑛 (=>k=1)
𝑇 𝑛 = Ꝋ(𝑛log𝑏𝑎 log 𝑛)
= Ꝋ(𝑛log22 𝑙𝑜𝑔1𝑛)
= Ꝋ(𝑛1 𝑙𝑜𝑔1𝑛 𝑙𝑜𝑔𝑛)
= Ꝋ(𝑛𝑙𝑜𝑔2𝑛)
Master Method (Another Approach)
𝒏
𝑻 𝒏 =𝒂𝑻 + Ꝋ(𝒏𝒌 𝒍𝒐𝒈𝒑 𝒏)
𝒃

a ≥ 1, b > 1 and k ≥ 0 and p is a real number

1. If a > bk, then 𝑇 𝑛 = Ꝋ(𝑛log𝑏𝑎 )
2. If a = bk,
a) If p > -1, then 𝑇 𝑛 = Ꝋ(𝑛log𝑏 𝑎 𝑙𝑜𝑔𝑝+1 n)
b) If p = -1, then 𝑇 𝑛 = Ꝋ(𝑛log𝑏 𝑎 loglog n)
c) If p < -1, then 𝑇 𝑛 = Ꝋ(𝑛log𝑏 𝑎 )

3. If a < bk,
a) If p ≥ 0, then 𝑇 𝑛 = Ꝋ(𝑛𝑘 𝑙𝑜𝑔𝑝 n)
b) If p < 0, then 𝑇 𝑛 = 𝑂(𝑛𝑘 )
Solving Recurrences using Master Method (Problem 1)
𝑛
Solve this recurrence: 𝑇 𝑛 =3𝑇 + 𝑛2
2

Solution
𝑎 = 3, 𝑏 = 2, 𝑘 = 2, 𝑝 = 0
𝑎 < 𝑏k
𝑇 𝑛 = Ꝋ(𝑛𝑘 𝑙𝑜𝑔𝑝 n)
= Ꝋ(𝑛2 𝑙𝑜𝑔0 n)
= Ꝋ(𝑛2 )
Solving Recurrences using Master Method (Problem 2)
𝑛
Solve this recurrence: 𝑇 𝑛 =4𝑇 + 𝑛2
2

Solution
𝑎 = 4, 𝑏 = 2, 𝑘 = 2, 𝑝 = 0
𝑎 = 𝑏k
𝑇 𝑛 = Ꝋ(𝑛log𝑏𝑎 𝑙𝑜𝑔𝑝+1 n)
= Ꝋ(𝑛𝑙𝑜𝑔24 𝑙𝑜𝑔0+1 n)
= Ꝋ(𝑛2 log 𝑛)
Solving Recurrences using Master Method (Problem 3)
𝑛
Solve this recurrence: 𝑇 𝑛 =𝑇 + 𝑛2
2

Solution
𝑎 = 1, 𝑏 = 2, 𝑘 = 2, 𝑝 = 0
𝑎 < 𝑏k
𝑇 𝑛 = Ꝋ(𝑛𝑘 𝑙𝑜𝑔𝑝 n)
= Ꝋ(𝑛2 𝑙𝑜𝑔0 n)
= Ꝋ(𝑛2 )
Solving Recurrences using Master Method (Problem 4)
𝑛
Solve this recurrence: 𝑇 𝑛 = 2𝑛𝑇 +𝑛
2

Solution
𝑎 = 2𝑛, 𝑎 𝑖𝑠 𝑛𝑜𝑡 𝑎 𝑐𝑜𝑛𝑠𝑡𝑎𝑛𝑡 ℎ𝑒𝑛𝑐𝑒 𝑚𝑎𝑠𝑡𝑒𝑟 𝑡ℎ𝑒𝑜𝑟𝑒𝑚 𝑑𝑜𝑒𝑠 𝑛𝑜𝑡 𝑎𝑝𝑝𝑙𝑦.
Solving Recurrences using Master Method (Problem 5)
𝑛
Solve this recurrence: 𝑇 𝑛 = 16 𝑇 +𝑛
4

Solution
𝑎 = 16, 𝑏 = 4, 𝑘 = 1, 𝑝 = 0
𝑎 > 𝑏k
𝑇 𝑛 = Ꝋ(𝑛log𝑏𝑎 )
= Ꝋ(𝑛𝑙𝑜𝑔416 )
= Ꝋ(𝑛2 )
Solving Recurrences using Master Method (Problem 6)
𝑛
Solve this recurrence: 𝑇 𝑛 =2𝑇 + 𝑛log n
2

Solution
𝑎 = 2, 𝑏 = 2, 𝑘 = 1, 𝑝 = 1
𝑎 = 𝑏k
𝑇 𝑛 = Ꝋ(𝑛log𝑏𝑎 𝑙𝑜𝑔𝑝+1 n)
= Ꝋ(𝑛𝑙𝑜𝑔22 𝑙𝑜𝑔1+1 n)
= Ꝋ(𝑛 log 2𝑛)