Divide & Conquer

Introduction

Divide and conquer is an algorithm design pattern that divides a problem into smaller subproblems, solves each of them, and then combines the results.

Three stages of divide and conquer:
1. Divide:  Divide the problem into a smaller a subproblems (each of size n/b)
2. Conquer:  Recursively solve each subproblem
3. Combine:  Combine the results of subproblems to form the overall solution

Recurrence relation: T(n) = a × T(n/b) + f(n)
a = number of subproblems
b = size reduction factor
f(n) = cost of dividing + merging

Master Theorem

In T(n) = a × T(n/b) + f(n), let c = log_b(a):

Case 1: f(n) = O(n^(c-ε))  →  T(n) = Θ(n^c)
(f grows polynomially slower than n^c)

Case 2: f(n) = Θ(n^c)      →  T(n) = Θ(n^c × log n)
(f is of the same order as n^c)

Case 3: f(n) = Ω(n^(c+ε))  →  T(n) = Θ(f(n))
(f grows polynomially faster than n^c)

Examples:
Merge sort: T(n) = 2T(n/2) + O(n) → c = log_2(2) = 1, f = O(n) → Case 2 → O(n log n)
Binary search: T(n) = T(n/2) + O(1)  → c = log_2(1) = 0, f = O(1) → Case 2 → O(log n)
Karatsuba:  T(n) = 3T(n/2) + O(n) → c = log_2(3) ≈ 1.585        → Case 1 → O(n^1.585)

Learning Goals

1. Understand the 3 steps of divide and conquer (Divide/Conquer/Merge) through merge sort and set up the recurrence relation T(n).
2. Implement fast exponentiation in O(log n), and apply it to modular exponentiation.
3. Determine the orientation of three points using the CCW (Counter-Clockwise) cross product.

Key Concepts

Merge Sort Analysis

Division: O(1) (only calculating indices)
Merge: O(n) (merging two sorted arrays)

T(n) = 2T(n/2) + O(n)
→ Master theorem case 2
     → T(n) = O(n log n)

Merge sort tree:
[8,3,5,1,9,2,6,4]           Level 0: n
[8,3,5,1] [9,2,6,4]         Level 1: n/2
[8,3] [5,1] [9,2] [6,4]     Level 2: n/4
  ...
Each level: O(n) merge × log n levels = O(n log n)

Fast Exponentiation

x^n = (x^(n/2))^2           if n is even
x^n = x × (x^(n/2))^2       if n is odd

Example: 2^10 = (2^5)^2 = ((2^2)^2 × 2)^2
→ Reduces from O(n) multiplications to O(log n) multiplications

CCW (Counter-Clockwise)

Given three points A, B, and C:
Cross product = (B-A) × (C-A)
       = (Bx-Ax)(Cy-Ay) - (By-Ay)(Cx-Ax)

> 0: CCW (counter-clockwise)
= 0: collinear
< 0: CW (clockwise)

Applications: Convex Hull, line segment intersection detection

Complexity Comparison

┌──────────────────────┬──────────────┬────────────────────────────┐
│ Algorithm             │ Time         │ Recurrence Relation               │
├──────────────────────┼──────────────┼────────────────────────────┤
│ Merge Sort            │ O(n log n)   │ T(n) = 2T(n/2) + O(n)           │
│ Fast Exponentiation   │ O(log n)     │ T(n) = T(n/2) + O(1)             │
│ Binary Search         │ O(log n)     │ T(n) = T(n/2) + O(1)             │
│ Karatsuba Multiplication │ O(n^1.585) │ T(n) = 3T(n/2) + O(n)           │
│ Closest Pair of Points │ O(n log n)   │ T(n) = 2T(n/2) + O(n log n)     │
└──────────────────────┴──────────────┴────────────────────────────┘

Example

Common Mistakes

1. Missing division base case: Recursion without if n <= 1: return can cause infinite loops or stack overflow
2. Order in modular exponentiation: Use of pow(a, b, m) is recommended since intermediate results can overflow
3. Index errors during merge: If leftover elements are not handled (extend) when merging two arrays, some elements may be missed
4. CCW integer overflow: Be careful of overflow in cross product calculation if coordinates are large (Python automatically expands integers)
5. Karatsuba Base Condition: Recursion should stop at single-digit numbers — stopping too early can actually slow it down

Summary

• Divide and Conquer: divide → solve recursively → merge
• Master Theorem: T(n) = aT(n/b) + f(n) → determines complexity in three cases
• Fast Exponentiation: O(n) → O(log n) — often used with modular operations
• CCW: key operation in geometric algorithms — used in convex hulls and line segment intersections

Try It Yourself

1. Quick Sort is also divide and conquer — T(n) Best/Worst analysis
2. Implementing the Closest Pair of Points in O(n log n)
3. Understanding the divide and conquer principle of FFT (Fast Fourier Transform)

Practice Problems

• Baekjoon 1629 (Multiplication) — Silver I
• Baekjoon 2630 (Making Colored Paper) — Silver II
• Baekjoon 1992 (Quadtree) — Silver I