Divide and Conquer

Divide and conquer has three steps, and only one of them is interesting:

1. Divide the problem into independent subproblems — usually trivial.
2. Conquer each recursively — also trivial, it is just a recursive call.
3. Combine the results — this is the algorithm.

Merge sort is not interesting because it splits in half; it is interesting because of merge. And the reason the pattern is worth its own page is that the combine step can compute things far beyond the stated problem: while merging two sorted halves, you can count cross-half relationships for free, which turns several $O(n^2)$ problems into $O(n \log n)$.

What you’ll learn

• The three-step skeleton, and how to reason about its cost with the Master Theorem.
• Why merge sort counts things — the technique behind inversion counting.
• Divide and conquer on expressions rather than arrays, where the split point is a choice.
• When D&C is the wrong tool, and what to use instead.
• Three real LeetCode problems solved in the browser: 912, 241, 493.

The cue

You are looking at divide and conquer when…

• The problem is naturally halvable and the halves are independent — 912, 148.
• You need to count or aggregate pairs across a split — 493, 315, 327. These are the interesting ones.
• An expression can be split at each operator, with each split giving a different result — 241, 95.
• A guarantee about both halves implies the answer — 53’s D&C variant, 1763.
• The problem says $O(\log(m + n))$ on two sorted inputs — 4, where you discard half of one array per step.

The anti-cue: if the subproblems overlap, plain D&C recomputes them exponentially — that is dynamic programming territory. Fibonacci by naive recursion is the canonical warning.

Visual intuition

Merge sort is the canonical divide and conquer, and watching it makes the recurrence concrete: the splits cost nothing, the merges are where all the work is, and there are $\log n$ levels of them.

sortMerge sort: O(n) work per level, log n levelsT(n) = 2T(n/2) + O(n)

3802714323394825106

1def merge_sort(a):2    if len(a) <= 1:3        return a4    mid = len(a) // 25    left  = merge_sort(a[:mid])6    right = merge_sort(a[mid:])7    return merge(left, right)8 9def merge(x, y):10    out, i, j = [], 0, 011    while i < len(x) and j < len(y):12        if x[i] <= y[j]:            # <= keeps it STABLE13            out.append(x[i]); i += 114        else:15            out.append(y[j]); j += 116    return out + x[i:] + y[j:]

setupMerge sort is bottom-up in effect: split until every piece is length 1 (trivially sorted), then merge sorted pieces pairwise. The merge is where all the work happens.

Play‹›1/14⟲

Count the comparisons at each level rather than in total -- every level touches all n elements once, and there are log n levels, which is the whole derivation of O(n log n). The counting variants on this page (inversions, reverse pairs) piggyback on exactly these merges, which is why they are also O(n log n).

The skeleton

divide_conquer.py

def solve(problem):
    if is_base_case(problem):          # small enough to answer directly
        return answer(problem)
 
    left, right = split(problem)       # 1. DIVIDE
    left_result = solve(left)          # 2. CONQUER
    right_result = solve(right)
 
    return combine(left_result, right_result)   # 3. COMBINE -- the real work

Reasoning about the cost

The Master Theorem gives the complexity from the recurrence $T(n) = a \cdot T(n/b) + f(n)$, where a is the number of subproblems, b the shrink factor, and f(n) the cost of combining.

Algorithm	Recurrence	Result
Binary search	$T(n) = T(n/2) + O(1)$	$O(\log n)$
Merge sort	$T(n) = 2T(n/2) + O(n)$	$O(n \log n)$
Naive matrix multiply	$T(n) = 8T(n/2) + O(n^2)$	$O(n^3)$
Strassen	$T(n) = 7T(n/2) + O(n^2)$	$O(n^{2.807})$

Strassen is instructive: it changes only a, from 8 subproblems to 7, and that alone beats the textbook cubic bound. When you want a D&C algorithm to be faster, you either reduce the number of subproblems or cheapen the combine.

Merge sort, and its real value

merge_sort.py

def merge_sort(a):
    if len(a) <= 1:
        return a
    mid = len(a) // 2
    left, right = merge_sort(a[:mid]), merge_sort(a[mid:])
 
    out, i, j = [], 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:            # <= keeps the sort STABLE
            out.append(left[i]); i += 1
        else:
            out.append(right[j]); j += 1
    out.extend(left[i:])                   # one side may remain
    out.extend(right[j:])
    return out

$O(n \log n)$ time and $O(n)$ space, and stable thanks to the <=.

Why merge sort matters more than quicksort here

Quicksort is usually faster in practice, but merge sort has two properties D&C problems exploit:

• Predictable splits. Always exactly half, so the recursion depth is guaranteed $\log n$ — no worst-case degradation.
• A combine step that sees both halves in sorted order. That is what lets you count cross-half relationships as a side effect.

The second point is the whole reason LC 493 and LC 315 are solvable in $O(n \log n)$. Quicksort’s partition gives you no such structured view.

Counting during the merge

Here is the idea worth taking from this page. When merging sorted left and sorted right, if left[i] > 2 * right[j], then every remaining element of left also exceeds 2 * right[j], because left is sorted ascending.

So instead of checking pairs one at a time, you count them in blocks:

count_during_merge.py

def count_reverse_pairs(a):
    """Count pairs i < j with a[i] > 2 * a[j]."""
    def sort_count(a):
        if len(a) <= 1:
            return a, 0
        mid = len(a) // 2
        left, cl = sort_count(a[:mid])
        right, cr = sort_count(a[mid:])
        count = cl + cr
 
        j = 0                              # a pointer that NEVER resets
        for x in left:                     # both halves are sorted here
            while j < len(right) and x > 2 * right[j]:
                j += 1
            count += j                     # x beats the first j elements
 
        merged, i, k = [], 0, 0            # then merge as usual
        while i < len(left) and k < len(right):
            if left[i] <= right[k]:
                merged.append(left[i]); i += 1
            else:
                merged.append(right[k]); k += 1
        merged.extend(left[i:]); merged.extend(right[k:])
        return merged, count
 
    return sort_count(a)[1]

The counting pointer must not reset

j is declared outside the for x in left loop. Because left is ascending, each successive x can only satisfy the condition for more elements of right, so j only ever moves forward.

Resetting j = 0 inside the loop still gives the right answer but makes the counting step $O(n^2)$, destroying the whole point. This is the same amortised two-pointer argument as sliding window: a pointer that never moves backwards costs $O(n)$ in total, not per iteration.

Every pair (i, j) with i in the left half and j in the right half is counted exactly once, at the merge that first separates them. Pairs within a half are counted by the recursive calls. So every pair is accounted for exactly once, which is why the total is correct.

Divide and conquer on expressions

For LC 241 the split point is not the midpoint — it is every operator in turn, and each choice yields a different set of results:

diff_ways_to_compute.py

from functools import lru_cache
 
 
def diff_ways_to_compute(expression):
    @lru_cache(maxsize=None)               # memoise: substrings recur a lot
    def solve(expr):
        if expr.lstrip("-").isdigit():     # base case: a bare number
            return (int(expr),)
 
        results = []
        for i, ch in enumerate(expr):
            if ch in "+-*":
                for a in solve(expr[:i]):          # every left result
                    for b in solve(expr[i + 1:]):  # crossed with every right
                        results.append(a + b if ch == "+" else
                                       a - b if ch == "-" else a * b)
        return tuple(results)
 
    return list(solve(expression))

The combine step is a cross product: every result from the left combined with every result from the right. That is characteristic of “all possible ways” problems.

Why memoise, and why return a tuple

The same substrings recur across different split choices, so lru_cache turns exponential recomputation into something manageable. Note the function must return a tuple, not a list, because lru_cache requires hashable return values only in the sense that arguments must be hashable — but returning an immutable tuple also prevents a caller mutating the cached value, which would corrupt later lookups. Returning a mutable list from a cached function is a genuine and subtle bug.

Also note expr.lstrip("-").isdigit() rather than expr.isdigit(): the latter is False for a negative number, which can appear once you allow expressions with leading minus signs. LC 241’s inputs are non-negative, but the guard costs nothing and is correct in general.

Dry run

LC 493 — reverse pairs in [1, 3, 2, 3, 1], i.e. pairs i < j with a[i] > 2·a[j]. The count is accumulated inside the merges, bottom-up:

depth	left (sorted)	right (sorted)	pairs found here	running total
1	[1]	[3]	0 — 1 > 6 is false	0
2	[3]	[1]	1 — 3 > 2·1 ✓	1
1	[2]	[1, 3]	0 — 2 > 2 is false	1
0	[1, 3]	[1, 2, 3]	1 — 3 > 2·1 ✓, and 1 beats nothing	2

Answer 2: the pairs are (3, 1) from indices 1 and 4, and (3, 1) from indices 3 and 4.

Four things this makes concrete:

• Both halves are already sorted when the counting runs, and that is the entire reason the block-counting works. left ascending means once x > 2·right[j] fails, it fails for every later x too — so j sweeps forward once instead of restarting per element.
• j must be declared outside the for x in left loop. Reset it per element and the counting becomes $O(n^2)$ per merge — still correct, but the whole point was to avoid that. This is the same amortised-pointer argument as a sliding window.
• Sorting destroys the original indices, and it does not matter. Pairs are counted before the two halves are merged, at the moment when every element of left genuinely precedes every element of right in the original array. That ordering guarantee is what licenses the count.
• The recursion counts each pair exactly once — at the unique level where its two elements first end up in different halves. The depth-0 merge finds one pair the deeper merges could not see, and re-counts none of theirs.

Complexity

Problem	Recurrence	Result
Merge sort	$T(n) = 2T(n/2) + O(n)$	$O(n \log n)$ time, $O(n)$ space
Reverse pairs / inversions	$T(n) = 2T(n/2) + O(n)$	$O(n \log n)$ — counting rides along free
Binary search	$T(n) = T(n/2) + O(1)$	$O(\log n)$
Quick sort, balanced pivots	$T(n) = 2T(n/2) + O(n)$	$O(n \log n)$ average, $O(n^2)$ worst
Quickselect	$T(n) = T(n/2) + O(n)$	$O(n)$ average
Karatsuba multiplication	$T(n) = 3T(n/2) + O(n)$	$O(n^{\log_2 3}) \approx O(n^{1.585})$
Different Ways to Add Parentheses	non-uniform splits	Catalan-many results, exponential

The Master Theorem in one line: for $T(n) = aT(n/b) + O(n^d)$, compare $d$ with $\log_b a$ — the larger exponent wins, and they tie into an extra $\log n$ factor. Merge sort is the tie case ($a = b = 2$, $d = 1$, so $\log_2 2 = 1 = d$), which is exactly why it lands on $n \log n$ rather than $n$ or $n^2$. Karatsuba beats naive multiplication precisely by changing $a$ from 4 to 3.

The recursion tree is the honest way to see it

$\log n$ levels; level $k$ has $2^k$ subproblems of size $n/2^k$, so each level does $2^k \times O(n/2^k) = O(n)$ work. $O(n)$ per level times $\log n$ levels is $O(n\log n)$ — and drawing that tree is faster and more convincing in an interview than quoting the theorem.

The same picture explains the space: $O(n)$ for merge sort’s buffers, but only $O(\log n)$ stack depth. And it shows why quick sort degrades — unbalanced pivots make the tree $n$ levels deep instead of $\log n$.

The variant map

Variant	The combine step	Canonical problem
Sort	Merge two sorted halves	912 · 148
Count cross-half pairs	Count during the merge	493 · 315 · 327
All possible results	Cross product of both sides	241 · 95
Best of left, right, or crossing	Compare three candidates	53 (D&C variant) · 1763
Discard half of one input	Binary search on the split position	4 Median of Two Sorted Arrays
Closest pair of points	Check the strip near the dividing line	classic geometry

LC 4 is the D&C problem people fear, and the framing helps

Median of Two Sorted Arrays in $O(\log(m+n))$ is not really “split the arrays” — it is binary search on how many elements of the smaller array belong to the left partition.

Choose i elements from nums1 and j = half - i from nums2. The partition is correct when nums1[i-1] <= nums2[j] and nums2[j-1] <= nums1[i] — both halves are then correctly separated, and the median comes from the boundary values. Binary search i, always over the shorter array so the range is small and j stays in bounds.

The reframe — from “divide the arrays” to “search for the split point” — is what makes it tractable. Also worth saying: the $O(m+n)$ merge-until-the-middle solution is far easier and is often accepted.

Practice — real LeetCode problems

LC 912 — Sort an Array · Medium

Problem. Sort an array of integers ascending. You must not use any built-in sorting function, and the solution should be $O(n \log n)$ with the lowest possible space complexity.

Constraints. 1 <= len(nums) <= 5 * 10^4, -5 * 10^4 <= nums[i] <= 5 * 10^4.

Examples. [5,2,3,1] gives [1,2,3,5] · [5,1,1,2,0,0] gives [0,0,1,1,2,5]

pch.exerciseTag pch.exerciseTitle

Editorial — approach, complexity, follow-ups

Split in half, sort each half, merge. The merge walks both halves once, always taking the smaller front element.

Time $O(n \log n)$ — $\log n$ levels, $O(n)$ merging per level. Space $O(n)$ for the temporary lists, plus $O(\log n)$ recursion.

<= rather than < makes the sort stable: equal elements keep their relative order. It makes no visible difference for plain integers, but it matters the moment you sort records by a key, and it is the correct default. LeetCode’s own [5,1,1,2,0,0] example contains duplicates specifically to exercise the merge.

Note this problem explicitly asks for “the smallest space complexity possible”, which is a nudge toward heap sort ($O(1)$ extra space) or an in-place quicksort with a randomised pivot. Worth mentioning both:

• Quicksort is $O(n \log n)$ average and $O(1)$ extra, but $O(n^2)$ worst case — and LC 912 has adversarial tests that kill a fixed pivot, so randomise.
• Heap sort is $O(n \log n)$ worst case and $O(1)$ extra, but not stable.

Merge sort is the safe answer for a D&C discussion; naming the trade-offs is what makes it a complete one. See Merge Sort and Quick Sort.

Follow-ups you should expect: “Sort a linked list (LC 148)?” — merge sort is the natural fit, since splitting needs no random access; find the middle with fast/slow pointers and merge with a dummy head. “Do it in place?” — in-place merging is possible but fiddly and slower; prefer heap sort if $O(1)$ space is required. “Why does Python’s sorted use Timsort?” — it exploits existing runs in real data, giving $O(n)$ on nearly-sorted input.

LC 241 — Different Ways to Add Parentheses · Medium

Problem. Given a string expression of numbers and the operators +, - and *, return all possible results from computing it with every valid parenthesisation. Results may be returned in any order.

Constraints. 1 <= len(expression) <= 20, non-negative integers under 10, and the number of results does not exceed 10^4.

Examples. "2-1-1" gives [0, 2] · "2*3-4*5" gives [-34,-14,-10,-10,10] (note the repeated -10) · "11" gives [11]

Why this test sorts the output

The problem accepts results in any order, so the test sorts before comparing. Note it does not deduplicate: "2*3-4*5" genuinely yields -10 twice, from two different parenthesisations, and both must appear.

pch.exerciseTag pch.exerciseTitle

Editorial — approach, complexity, follow-ups

Each operator is a candidate root of the expression tree. Choosing it splits the string into a left and a right subexpression, each of which has its own set of possible values. The results for this choice are every left value combined with every right value.

Time exponential in general — the count of distinct parenthesisations follows the Catalan numbers — but bounded here by the promise of at most $10^4$ results, and cut substantially by memoisation. Space $O(\text{results})$ plus the cache.

Two details:

• "11" must give [11]. The base case has to handle multi-digit numbers, so it tests the whole substring rather than a single character. isdigit() on the string does that.
• Do not deduplicate. "2*3-4*5" yields -10 from two different parenthesisations and the expected output lists it twice. Wrapping the result in a set is a plausible-looking mistake that fails this exact example.

Returning a tuple from the memoised function is deliberate: a cached mutable list could be modified by a caller and corrupt every later lookup.

Without memoisation this is still accepted at len <= 20, so it is optional here — but recognising that the subproblems overlap is the observation that connects D&C to dynamic programming. When they overlap heavily, memoising is what stops D&C from being exponential.

Follow-ups you should expect: “Return the expressions, not just the values?” — build strings alongside the numbers in the combine step. “Handle division?” — add the operator and guard against dividing by zero. “Count the ways rather than list them?” — the n-th Catalan number over the operator count, no enumeration needed. “Generate all BSTs from 1..n (LC 95)?” — structurally identical: each value is a candidate root, and the combine is a cross product of left and right subtrees.

LC 493 — Reverse Pairs · Hard

Problem. A reverse pair is a pair (i, j) with i < j and nums[i] > 2 * nums[j]. Return the number of reverse pairs.

Constraints. 1 <= len(nums) <= 5 * 10^4, -2^31 <= nums[i] <= 2^31 - 1.

Examples. [1,3,2,3,1] gives 2 · [2,4,3,5,1] gives 3 · [5,4,3,2,1] gives 4

pch.exerciseTag pch.exerciseTitle

Editorial — approach, complexity, follow-ups

Every reverse pair has its two indices either within one half or across the split. Recursion handles the within-half pairs; the merge step counts the cross-half ones. So every pair is counted exactly once, at the level where the two indices first end up in different halves.

The counting is cheap because both halves are already sorted: for ascending x from left, the set of qualifying right elements only grows, so one forward-only pointer suffices.

Time $O(n \log n)$ — the counting adds $O(n)$ per merge level, the same order as the merge itself. Space $O(n)$.

Two details that decide whether this works:

• j outside the loop. Resetting it makes the count step $O(n^2)$ and the whole thing $O(n^2 \log n)$ — worse than brute force. The amortised forward-only-pointer argument is the same one behind sliding window.
• Count before merging. The counting loop relies on left and right being separate sorted lists. Once merged, the split information is gone.

Test-case notes: [5,4,3,2,1] gives 4 — pairs (5,2), (5,1), (4,1), (3,1), since e.g. 5 > 2*2. [1,1,1] gives 0, confirming the strict inequality. And note the constraints allow the full 32-bit range, so 2 * nums[j] can exceed 32 bits — a non-issue in Python, but in C++ or Java you would need a 64-bit cast, which is a good detail to raise.

Follow-ups you should expect:

• “Count plain inversions (nums[i] > nums[j])?” The same algorithm with the factor of 2 removed — the classic inversion count.
• “Count of smaller numbers after self (LC 315)?” Same merge-sort-with-counting idea, but you must track original indices to attribute counts per element.
• “Do it with a Fenwick tree instead?” Yes: compress the values and query prefix counts as you sweep right to left. $O(n \log n)$ too, and often easier to extend. Worth naming as the alternative.
• “Why not brute force?” $O(n^2)$ is $2.5 \times 10^9$ operations at $n = 5 \times 10^4$ — far too slow.

LeetCode problem set

Generated from the problem database, so each entry carries its sheet membership and reported companies. Tick them off as you go — progress is saved in this browser, and the Export button writes it to a file you can keep.

LC 148 is where merge sort beats quicksort outright

Sorting a linked list in $O(n \log n)$ with $O(1)$ extra space is merge sort’s home turf. Quicksort needs random access to partition efficiently; merge sort only needs to split (fast/slow pointers) and merge (a dummy head), both of which are natural on a list.

It is also a nice composition of three patterns already covered: fast and slow pointers to find the middle, dummy-head merging to combine, and this page’s D&C skeleton to organise it.

7 problems

1 easy4 medium2 hard

Work down the ladder. Tick each problem off as you go — progress is saved in this browser, and the Export button in the filter bar writes it to a file you can keep.

AllEasyMediumHard

Unsolved onlyExportImportReset

• ○108Convert Sorted Array to Binary Search TreeeasyLeetCode Top Interview 150
• ○148Sort ListmediumMerge sort on a linked list -- no random access neededLeetCode Top Interview 150
• ○241Different Ways to Add ParenthesesmediumSplit at every operator; combine is a cross product; do **not** deduplicate
• ○427Construct Quad TreemediumLeetCode Top Interview 150
• ○912Sort an ArraymediumMerge sort; `<=` for stability
• ○4Median of Two Sorted ArrayshardBinary search the split position in the **shorter** arrayNeetCode 150LeetCode Top Interview 150googleamazonmicrosoftbytedance
• ○315Count of Smaller Numbers After SelfhardSame idea, but attribute counts to original indices

Interview follow-ups

They ask	What they’re checking	The answer
“Where is the actual work?”	Understanding the pattern	In the combine step; divide and conquer are usually trivial
“Derive the complexity”	Master Theorem fluency	$T(n) = aT(n/b) + f(n)$; merge sort is $2T(n/2) + O(n) = O(n \log n)$
“How does merge sort count inversions?”	The key technique	Cross-half pairs are counted at the merge with a forward-only pointer, so $O(n)$ per level
“Why must the pointer not reset?”	Amortised reasoning	Both halves are sorted, so it only moves forward — resetting makes the step $O(n^2)$
“What if the subproblems overlap?”	Knowing the boundary	Plain D&C recomputes exponentially; memoise, i.e. use DP
“Merge sort or quicksort?”	Judgement	Merge for stability, predictable splits and linked lists; quicksort for $O(1)$ space in-place, with a randomised pivot
“Alternative to merge-counting?”	Breadth	A Fenwick tree over compressed values, sweeping from the right

Edge-case checklist

• Single element — the base case for every recursion here.
• Empty input — guard len(a) <= 1 covers it.
• All identical — [3,3,3] sorts fine and yields 0 reverse pairs (strict inequality).
• Already sorted / reverse sorted — the extremes for counting; [5,4,3,2,1] gives 4.
• Negative values — legal in 912 and 493; 2 * nums[j] gets smaller for negatives, so do not assume monotonic behaviour.
• 32-bit overflow in 2 * nums[j] — a non-issue in Python, real elsewhere.
• Multi-digit numbers (LC 241) — "11" must parse as one number.
• Duplicate results (LC 241) — must be kept, not deduplicated.
• Recursion depth — $\log n$ for merge sort, so never a problem; but expression recursion is bounded by string length.

Self-check

pch.quizTag Divide and conquer — self-check

1. Why is merge sort O(n log n) rather than O(n) or O(n²)?

   A Because sorting is inherently O(n log n) B Because each of the log n levels does O(n) work: level k has 2^k subproblems of size n/2^k, so every level touches all n elements once C Because the merge is O(log n) D Because the recursion depth is n
   pch.quizShowAnswer

   B — Because each of the log n levels does O(n) work: level k has 2^k subproblems of size n/2^k, so every level touches all n elements once — Drawing the recursion tree and multiplying 'work per level × number of levels' is faster and more convincing than quoting the Master Theorem — and it also explains the O(n) space and O(log n) stack depth.

2. In the reverse-pairs count, why can `j` sweep forward without ever resetting?

   A Because the array is small B Because `left` is sorted ascending, so once x > 2·right[j] fails it fails for every later x too — the pointer is amortised across the whole merge C Because j is bounded by log n D It does reset; that is the bug
   pch.quizShowAnswer

   B — Because `left` is sorted ascending, so once x > 2·right[j] fails it fails for every later x too — the pointer is amortised across the whole merge — Declaring j inside the loop keeps the answer correct but makes each merge O(n²), which defeats the purpose. Same amortised-pointer argument as a sliding window.

3. Sorting during the count destroys the original indices. Why is the answer still right?

   A Because the pairs are re-checked at the end B Because pairs are counted BEFORE the halves merge — at that moment every element of `left` genuinely precedes every element of `right` in the original array C Because sorting is stable D Because inversions are order-independent
   pch.quizShowAnswer

   B — Because pairs are counted BEFORE the halves merge — at that moment every element of `left` genuinely precedes every element of `right` in the original array — Each pair is also counted exactly once, at the unique recursion level where its two elements first land in different halves. That is why no deduplication is needed.

4. For T(n) = aT(n/b) + O(n^d), how do you get the answer quickly?

   A It is always O(n log n) B Compare d with log_b(a): the larger exponent dominates, and a tie adds a log n factor — merge sort is the tie case (a=b=2, d=1) C Multiply a by d D Take the maximum of a and b
   pch.quizShowAnswer

   B — Compare d with log_b(a): the larger exponent dominates, and a tie adds a log n factor — merge sort is the tie case (a=b=2, d=1) — Karatsuba is the memorable non-tie case: changing a from 4 to 3 with b=2 moves the exponent from n² to n^1.585 with no change to d.

5. Quick sort has the same recurrence as merge sort but O(n²) worst case. Why?

   A Because it is not stable B Because the recurrence only holds when pivots split evenly — a bad pivot makes the tree n levels deep instead of log n, and O(n) work at each of n levels is O(n²) C Because it sorts in place D Because it uses more comparisons per merge
   pch.quizShowAnswer

   B — Because the recurrence only holds when pivots split evenly — a bad pivot makes the tree n levels deep instead of log n, and O(n) work at each of n levels is O(n²) — The recurrence describes the balanced case. Divide and conquer's guarantee depends entirely on the division actually being balanced, which merge sort gets structurally and quick sort only probabilistically.

6. Which problems on this page are NOT improved by divide and conquer?

   A None; it always helps B Ones where the subproblems overlap — then it is exponential re-computation and you want DP (memoisation) instead; divide and conquer assumes independent subproblems C Ones with more than two subproblems D Ones on strings rather than arrays
   pch.quizShowAnswer

   B — Ones where the subproblems overlap — then it is exponential re-computation and you want DP (memoisation) instead; divide and conquer assumes independent subproblems — That distinction is the boundary with the whole DP phase: independent subproblems → divide and conquer; overlapping ones → cache them and it becomes DP.

Recall card

• Cue — the problem splits into independent subproblems of the same shape, and the results combine cheaply: sorting, counting pairs across halves, searching a halved space, expression parenthesisation.
• Skeleton — base case → split → recurse on each part → combine. The combine step is where the real work (and the complexity) lives.
• Cost — recursion tree: work per level × number of levels. Master Theorem for $T(n) = aT(n/b) + O(n^d)$: compare $d$ with $\log_b a$, larger wins, ties add $\log n$.
• Merge sort — $O(n \log n)$ time, $O(n)$ space, $O(\log n)$ stack; the tie case of the theorem.
• Counting during the merge — inversions and reverse pairs ride along free, because both halves are sorted at that moment. Keep the counting pointer outside the loop.
• Balance is the whole guarantee — quick sort shares the recurrence and degrades to $O(n^2)$ when pivots are bad.
• Boundary — overlapping subproblems mean this is the wrong frame; cache them and it becomes DP.

Recap

• Divide and conquer is split, solve, combine — and the combine step is the algorithm.
• Use the Master Theorem to get the complexity from the recurrence; to speed a D&C algorithm up, reduce the number of subproblems or cheapen the combine.
• Merge sort counts things. Cross-half relationships can be tallied during the merge in $O(n)$ per level, turning $O(n^2)$ pair-counting into $O(n \log n)$. The counting pointer must never reset.
• Every pair is counted exactly once — at the level where its indices first fall into different halves.
• For “all possible ways” problems, split at every valid point and make the combine a cross product. Memoise when substrings recur.
• If subproblems overlap, plain D&C is exponential — that is DP’s territory.
• <= in the merge keeps the sort stable.

Next: the dynamic programming phase — what to do when the subproblems overlap.