Divide and conquer — template, correctness, recurrence

The Template

def solve(P):
    # 1. BASE CASE — small enough to answer directly
    if size(P) <= threshold:
        return brute_force(P)
 
    # 2. DIVIDE — break into a subproblems of size n/b
    subproblems = split(P)              # cost = D(n)
 
    # 3. CONQUER — recurse on each
    results = [solve(sub) for sub in subproblems]
 
    # 4. COMBINE — glue answers
    return combine(results)             # cost = C(n)

Correctness — why it actually works

Three obligations you must discharge — miss one and the proof (and the code) breaks:

Obligation	What it guarantees
Progress	every recursive call has size strictly $< n$ → recursion terminates
Base correctness	the smallest cases are right
Combine correctness	correct parts ⟹ correct whole

$T(n)=aT(n/b)+f(n)$ Expand level by level. At depth $i$ there are $a^i$ nodes, each on input size $n/b^i$ , doing $f(n/b^i)$ non-recursive work: $\text{level } i \text{ cost} = a^i\, f\!\left(\frac{n}{b^i}\right)$ Recursion stops when $n/b^i = 1 \Rightarrow i = \log_b n$ levels. The leaves number $a^{\log_b n} = n^{\log_b a}$ , each costing $\Theta(1)$ : $\text{leaf cost} = \Theta\!\left(n^{\log_b a}\right)$ Total: $T(n)=\Theta\!\left(n^{\log_b a}\right)+\sum_{i=0}^{\log_b n -1} a^i f\!\left(\frac{n}{b^i}\right)$

Figure — Divide and conquer — template, correctness, recurrence

The Master Theorem (the shortcut)

Formula Three cases — compare

$f(n)$ against $n^{\log_b a}$ Let $c_{\text{crit}}=\log_b a$ (the "watershed" exponent — the cost of the leaves).

Leaf-heavy: if $f(n)=O(n^{c_{\text{crit}}-\varepsilon})$ for some $\varepsilon>0$ , then $T(n)=\Theta(n^{c_{\text{crit}}})$ .
Balanced: if $f(n)=\Theta(n^{c_{\text{crit}}})$ , then $T(n)=\Theta(n^{c_{\text{crit}}}\log n)$ .
Root-heavy: if $f(n)=\Omega(n^{c_{\text{crit}}+\varepsilon})$ and $a f(n/b)\le k f(n)$ for some $k<1$ (regularity), then $T(n)=\Theta(f(n))$ .

WHY: the total is dominated by either the leaves (case 1), spread evenly across $\log n$ levels (case 2), or the root (case 3) — exactly which side of $n^{\log_b a}$ that $f$ lands on.

When Master Theorem fails

Flashcards

What are the three phases of a divide-and-conquer algorithm?

Divide (split into subproblems), Conquer (solve each recursively to a base case), Combine (merge sub-answers).

In the recurrence

T(n)=aT(n/b)+f(n)

, what do

a

b

, and

f

mean?

a

= number of subproblems,

b

= factor input shrinks by,

f(n)

= cost of divide + combine (non-recursive work).

What is the "watershed" exponent in the Master Theorem?

c_{\text{crit}}=\log_b a

, the cost of the leaves

n^{\log_b a}

; you compare

f(n)

against

n^{c_{\text{crit}}}

Master Theorem Case 2 condition and result?

f(n)=\Theta(n^{\log_b a})

then

T(n)=\Theta(n^{\log_b a}\log n)

Why does mergesort give

\Theta(n\log n)

a=b=2

c_{\text{crit}}=1

f(n)=\Theta(n)

matches → Case 2 →

n\cdot\log n

levels of

\Theta(n)

work.

What three obligations make a divide-and-conquer algorithm correct by induction?

Progress (subproblems strictly smaller), Base correctness, Combine correctness.

Why does Karatsuba beat schoolbook multiplication?

It uses 3 half-size multiplications instead of 4, dropping

a

from 4 to 3 so the exponent falls from

\log_2 4=2

\log_2 3\approx1.585

When does the Master Theorem NOT apply?

When

f(n)

differs from

n^{\log_b a}

only by a non-polynomial (e.g. log) factor, or splits are uneven — use recursion tree or Akra–Bazzi.

How many leaves does the recursion tree of

aT(n/b)

have?

a^{\log_b n}=n^{\log_b a}

What proof technique establishes divide-and-conquer correctness?

Strong induction on input size

n

(IH: correct for all sizes

<n

Recall Feynman: explain it to a 12-year-old

Imagine you have a giant pile of mixed-up cards and you must sort them. Too big to handle alone. So you split the pile in half and hand each half to a friend. They each split their half and hand it on... until someone gets just one card (already "sorted"!). Then everyone hands sorted little piles back up, and at each step you just zip two sorted piles together like a zipper — easy, because both sides are already in order. Splitting was free, zipping is quick, and because you halved again and again, you only needed about $\log n$ rounds. That's why it's so fast!

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Divide and conquer ka funda simple hai: ek bada problem solve karna mushkil hai, toh use chhote-chhote same type ke subproblems mein tod do, har ek ko recursively solve karo, aur phir unke answers ko combine kar do. Teen steps yaad rakho — Divide, Conquer, Combine. Sabse important baat: ek base case zaroor hona chahiye (jaise array of size 1 already sorted hota hai), warna recursion kabhi rukega hi nahi aur stack overflow ho jayega.

Correctness ka proof hum strong induction se karte hain. Maan lo ki size $n$ se chhote sabhi inputs pe algorithm sahi answer deta hai (yeh hamari assumption — IH hai). Phir agar divide chhote valid subproblems banata hai, toh recursive calls IH se sahi answer denge, aur agar combine sahi parts se sahi whole banata hai — bas, proof done. Mergesort mein hum halves ko dobara check nahi karte; IH bolta hai woh already sorted hain, sirf merge ka correctness prove karna padta hai.

Time nikalne ke liye recurrence likho: $T(n)=a\,T(n/b)+f(n)$ , jahan $a$ = kitne subproblems, $b$ = size kitne se divide hua, aur $f(n)$ = divide + combine ka cost. Recursion tree banao — har level pe kitna kaam ho raha hai add karo. Master Theorem shortcut deta hai: $f(n)$ ko $n^{\log_b a}$ se compare karo. Chhota hai toh leaves dominate (Case 1), barabar hai toh extra $\log n$ multiply (Case 2), bada hai toh root dominate (Case 3).

Examples se clear hoga: Mergesort $2T(n/2)+n$ → $\log_2 2=1$ , $f=n$ match → $n\log n$ . Binary search $T(n/2)+1$ → sirf ek call → $\log n$ . Karatsuba ka jugaad: 4 ki jagah sirf 3 multiplications karke exponent $2$ se $1.585$ tak gira deta hai — yahi divide-and-conquer ki asli power hai, smart combine se kaam bachana.

Divide and conquer — template, correctness, recurrence

The Template

Correctness — why it actually works

The Recurrence

Solving by the recursion tree (first principles)

The Master Theorem (the shortcut)

When Master Theorem fails

Flashcards

Concept Map

Hinglish (regional understanding)

Go deeper — visual, from zero

Test yourself — Algorithm Paradigms

Connections