23. Divide & Conquer

What you'll learn

• 1Apply D&C to merge/quick sort
• 2Compute aⁿ in O(log n) with fast exponentiation
• 3Use CCW for geometric orientation

Overview

Divide & Conquer's recurrence is T(n) = aT(n/b) + f(n). The Master Theorem tells you the resulting complexity. Merge sort is T(n) = 2T(n/2) + O(n) = O(n log n).

Core Concepts

1. Fast exponentiation

def fast_power(a, n, mod=None):
    """Compute a^n in O(log n)."""
    result = 1
    while n > 0:
        if n & 1:
            result = result * a
            if mod: result %= mod
        a = a * a
        if mod: a %= mod
        n >>= 1
    return result

# Python's pow(a, n, mod) is faster (C-implemented):
pow(2, 100, 10**9 + 7)

2. Matrix exponentiation

Generalizes fast exponentiation to compute the n-th Fibonacci number in O(log n).

def mat_mul(A, B):
    return [[sum(A[i][k] * B[k][j] for k in range(2)) for j in range(2)] for i in range(2)]

def mat_pow(M, n):
    result = [[1, 0], [0, 1]]   # identity
    while n > 0:
        if n & 1:
            result = mat_mul(result, M)
        M = mat_mul(M, M)
        n >>= 1
    return result

# Fibonacci in O(log n)
fib_matrix = [[1, 1], [1, 0]]
fib_n = mat_pow(fib_matrix, n)[0][1]

3. CCW (Counter-Clockwise) — geometry

def ccw(a, b, c):
    """Returns:
        > 0  if a→b→c is counter-clockwise (left turn)
        < 0  if clockwise (right turn)
        = 0  if collinear"""
    return (b[0] - a[0]) * (c[1] - a[1]) - (b[1] - a[1]) * (c[0] - a[0])

Foundation for line-segment intersection, convex hull, and many computational geometry problems.

4. The Master Theorem (intuition)

Examples

Example 1 — src/01_fast_power.py

Fast exponentiation iteratively and recursively.

Example 2 — src/02_matrix_power.py

Fibonacci in O(log n) via matrix exponentiation.

Example 3 — src/03_ccw.py

Detect line-segment intersection using CCW.

Example 4 — src/04_quickselect.py

Find the k-th smallest element in O(n) average.

Common Mistakes

1. Forgetting % mod between multiplications — overflow in other languages, slow in Python.
2. Off-by-one in matrix exponentiation initial state (identity vs first matrix).
3. CCW sign confusion — verify with a tiny example.
4. Recursion overhead vs iteration — iterative fast_power is preferred.

Recap

• D&C: split, solve, combine.
• Fast exponentiation: O(log n) for powers.
• Matrix exponentiation generalizes to linear recurrences.
• CCW: cross product gives orientation.

Try It

1. BOJ 1629 (Fast exponentiation).
2. BOJ 11444 (Fast Fibonacci).
3. BOJ 11758 (CCW direction).