Divide and Conquer

←Back to Tech Tree

inventorycoverage

Divide and Conquer #

AlgorithmsDifficulty: ★★★☆☆Depth: 4Unlocks: 0

Breaking problems into subproblems. Merge sort, quicksort.

Interactive Visualization #

⏮◀◀▶▶STEP0.25x1xZOOM

t=0s

Core Concepts #

Essential Relationships #

Prerequisites (2) #

Recursion5 atomsRecurrence Relations5 atoms

Advanced Learning Details

Graph Position #

52

Depth Cost

0

Fan-Out (ROI)

0

Bottleneck Score

4

Chain Length

Cognitive Load #

5

Atomic Elements

34

Total Elements

L2

Percentile Level

L3

Atomic Level

All Concepts (16) #

Teaching Strategy #

Quick unlock - significant prerequisite investment but simple final step. Verify prerequisites first.

Some problems feel too big to solve in one shot—but surprisingly easy if you cut them into clean pieces, solve each piece the same way, and then stitch the answers back together. Divide and conquer is that idea made precise, and it powers classic fast algorithms like merge sort and quicksort.

TL;DR:

Divide and conquer solves a problem by (1) splitting it into smaller subproblems, (2) solving each subproblem recursively, and (3) combining the results. When the split is balanced, you often get fast runtimes like T(n) = 2T(n/2) + O(n) ⇒ O(n log n). Merge sort is the canonical example; quicksort is similar but combines “for free” and pays in the partition step.

What Is Divide and Conquer? #

Divide and conquer is an algorithm design pattern:

  1. Decompose (Divide): Break the original problem of size n into smaller subproblems (often of size about n/2).

  2. Conquer: Solve each subproblem—typically by calling the same algorithm recursively.

  3. Combine: Assemble the subproblem solutions into a solution for the original problem.

Why this pattern exists (motivation first) #

Many problems have two key properties:

If those hold, you can trade one “hard” problem of size n for several “easier” ones of size n/b. If the work to combine is not too expensive, the total work can drop dramatically.

A mental model #

Imagine a problem is a tangled rope. Trying to untangle it all at once is frustrating. Divide and conquer says: cut it into segments, untangle each segment with the same technique, then tie the segments back together.

The recursion-tree viewpoint #

Divide and conquer algorithms naturally form a recursion tree:

If you split into a constant number of subproblems each time, and each split reduces size by a constant factor, the depth of the tree is about log₂ n.

A generic template #

Here’s a language-agnostic skeleton:

The key design choices are:

Divide and conquer vs “just recursion” #

You already know recursion, but not every recursive algorithm is divide and conquer.

A practical rule of thumb:

This difference is often the difference between O(n log n) and O(n²) (or between O(log n) and O(n)).

Core Mechanic 1: Decompose + Conquer (How Splitting Shapes Runtime) #

The “divide” step is not just a structural decision—it largely determines performance.

Balanced vs unbalanced splits #

Suppose you split a problem of size n into subproblems with sizes:

Even if the combine step is similar, the recursion depth changes dramatically.

Balanced split intuition #

If each level halves the input size, then after k levels you’re at size n/2ᵏ. You stop when n/2ᵏ ≈ 1.

Solve for k:

n/2ᵏ ≈ 1

⇒ 2ᵏ ≈ n

⇒ k ≈ log₂ n

So you get about log₂ n levels.

Unbalanced split intuition #

If each step reduces n by 1, then you need about n steps to reach the base case. That’s depth O(n).

Recurrences as the language of divide and conquer #

Divide and conquer costs are commonly written as a recurrence:

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

Where:

A famous example is merge sort:

T(n) = 2T(n/2) + O(n)

Why “O(n log n)” often appears #

Let’s build intuition before formal rules.

For merge sort:

Total combine work per level ≈ O(n), and there are ≈ log₂ n levels.

So total ≈ O(n log n).

A slightly more “show your work” derivation #

Consider:

T(n) = 2T(n/2) + cn

Expand one step:

T(n) = 2[2T(n/4) + c(n/2)] + cn

= 4T(n/4) + 2c(n/2) + cn

= 4T(n/4) + cn + cn

= 4T(n/4) + 2cn

Expand again:

T(n) = 4[2T(n/8) + c(n/4)] + 2cn

= 8T(n/8) + 4c(n/4) + 2cn

= 8T(n/8) + cn + 2cn

= 8T(n/8) + 3cn

After k expansions:

T(n) = 2ᵏ T(n/2ᵏ) + kcn

Stop when n/2ᵏ = 1 ⇒ 2ᵏ = n ⇒ k = log₂ n.

Then:

T(n) = nT(1) + cn log₂ n

If T(1) is constant:

T(n) = O(n) + O(n log n) = O(n log n)

Practical design note: base cases and thresholds #

Even with a beautiful recurrence, real implementations often stop recursion early.

Example: in merge sort, you might stop when subarray length ≤ 32 and use insertion sort.

Why?

This doesn’t change asymptotic complexity, but it often improves actual performance.

Independence of subproblems #

Divide and conquer works best when subproblems are mostly independent.

When subproblems overlap heavily, divide and conquer alone may recompute work. That’s where dynamic programming can enter—but that’s a different node.

Core Mechanic 2: Combine (The Often-Underappreciated Step) #

“Combine” is where divide and conquer either wins big or quietly loses its advantage.

Why combine matters #

Even if you split into smaller pieces, if you recombine in a costly way you can erase the benefit.

A useful way to think:

The art is to keep combine cheap enough that shrinking n dominates.

Two classic combine patterns #

PatternExampleCombine costNotes
Explicit mergemerge sortO(n)Must merge two sorted lists; linear and predictable
Implicit combinequicksortO(1) “combine”The work is mostly in partition; after partition, concatenation is conceptually trivial

Merge sort’s combine: merging two sorted arrays #

Suppose you have two sorted arrays:

You can merge them in O(n) time by walking two pointers i and j:

Each element is moved exactly once → linear time.

The reason this is so powerful is subtle:

So the cost per level doesn’t blow up.

Quicksort’s combine: why it’s considered “free” #

Quicksort does something slightly different:

  1. Partition around a pivot p so that:

  1. Recursively sort left and right

  2. Combine by placing: sorted(left), then pivot, then sorted(right)

Combine is just concatenation, which is O(1) conceptually (or O(n) depending on in-place vs out-of-place details), but the key is: the main linear work is in partitioning, not merging.

So quicksort’s recurrence is commonly:

T(n) = T(k) + T(n−k−1) + O(n)

where k is the number of elements less than pivot.

Best/average vs worst case: the combine tradeoff #

Because quicksort’s split depends on pivot choice, you can get:

Merge sort, in contrast, always splits in half regardless of input:

T(n) = 2T(n/2) + O(n) ⇒ O(n log n) always

So there’s a stability-vs-typical-speed trade:

AlgorithmTypical timeWorst-case timeExtra memoryStability
Merge sortO(n log n)O(n log n)O(n) (array version)Stable
QuicksortO(n log n) averageO(n²)O(log n) stack (in-place)Not stable by default

Combine can be more than “merge lists” #

In other divide and conquer problems, combine might be:

A famous example (not required here, but instructive): maximum subarray can be done with divide and conquer by combining left max, right max, and crossing max. Combine takes linear time unless you maintain extra boundary sums.

Designing combine: what to ask yourself #

When inventing or analyzing a divide and conquer algorithm, ask:

  1. What exact information must each subproblem return to make combine cheap?

  2. Can I avoid recomputing work in combine?

  3. Does combine touch every element at every level (→ likely O(n log n))?

  4. Is the split guaranteed balanced, or does input affect it?

Those questions often predict runtime before any formal solving.

Application/Connection: Merge Sort and Quicksort as Case Studies #

This section ties the pattern to two flagship algorithms and shows what “divide, conquer, combine” looks like concretely.

Merge sort #

Why merge sort exists #

Sorting is a common subroutine. Many simple sorts (like insertion sort) are O(n²) in the worst case. Merge sort achieves O(n log n) deterministically by leaning hard on divide and conquer.

Divide #

Split the array A into two halves:

Conquer #

Recursively merge sort each half.

Combine #

Merge the two sorted halves with the linear two-pointer merge.

Complexity summary #

Let f(n) be merge cost: f(n) = cn.

T(n) = 2T(n/2) + cn

⇒ T(n) = O(n log n)

Stability (practical property) #

Merge sort can be stable: if L[i] == R[j], take from L first, preserving original relative order.

This matters when sorting records by multiple keys.

Quicksort #

Why quicksort exists #

Quicksort is often the fastest comparison sort in practice due to:

But its performance depends on getting good splits.

Divide (partition) #

Choose a pivot p. Rearrange the array so:

This partition step is O(n).

Conquer #

Recursively quicksort the left and right parts.

Combine #

No merge step needed; the array is already partitioned. Conceptually:

sorted(left) + [p] + sorted(right)

Complexity summary #

Average case (random pivot or randomized input):

E[T(n)] = O(n log n)

Worst case (already sorted + poor pivot rule like “first element”):

T(n) = T(n−1) + cn

Show the sum expansion:

T(n) = T(n−1) + cn

= T(n−2) + c(n−1) + cn

= ...

= T(1) + c(2 + 3 + ... + n)

Use arithmetic series:

∑_{k=2}^{n} k = (n(n+1)/2) − 1

So:

T(n) = O(n²)

Engineering fix: randomization #

Randomly choosing the pivot (or shuffling the array first) makes worst-case behavior extremely unlikely, giving strong practical performance.

When to choose which #

SituationPreferReason
Need guaranteed O(n log n)Merge sortWorst-case safe
Need stabilityMerge sortStable by design
Tight memory, in-place desiredQuicksortO(log n) stack typical
Average performance is priorityQuicksortOften faster constants

Connection to other divide and conquer ideas #

Even if you only remember merge sort and quicksort, the bigger skill is: recognizing when a problem can be split into mostly independent subproblems and recombined cheaply.

Worked Examples (3) #

Solve a classic divide-and-conquer recurrence: T(n) = 2T(n/2) + n #

Assume n is a power of 2, and T(1) = 1. Find a closed form (up to Θ(·)) and explain the intuition.

  1. Start with the recurrence:

    T(n) = 2T(n/2) + n

  2. Expand one level:

    T(n) = 2[2T(n/4) + (n/2)] + n

    = 4T(n/4) + n + n

    = 4T(n/4) + 2n

  3. Expand a second level:

    T(n) = 4[2T(n/8) + (n/4)] + 2n

    = 8T(n/8) + n + 2n

    = 8T(n/8) + 3n

  4. After k expansions, the pattern is:

    T(n) = 2ᵏ T(n/2ᵏ) + kn

  5. Stop expanding at the base case when n/2ᵏ = 1:

    2ᵏ = n

    k = log₂ n

  6. Substitute k back in:

    T(n) = 2^{log₂ n} T(1) + n log₂ n

    = n·1 + n log₂ n

    = n + n log₂ n

    = Θ(n log n)

Insight: The combine work is n per level, and there are log₂ n levels, so total work is n log n. This is the signature runtime of balanced divide-and-conquer with linear combine.

Trace merge sort’s divide/conquer/combine on a small array #

Sort A = [8, 3, 7, 4, 2, 6, 5, 1] using merge sort. Show the splits and one representative merge step in detail.

  1. Divide repeatedly into halves:

    [8, 3, 7, 4, 2, 6, 5, 1]

    → [8, 3, 7, 4] and [2, 6, 5, 1]

    → [8, 3] [7, 4] and [2, 6] [5, 1]

    → [8] [3] [7] [4] [2] [6] [5] [1]

  2. Conquer (base cases): arrays of length 1 are already sorted:

    [8], [3], [7], [4], [2], [6], [5], [1]

  3. Combine: merge pairs:

    merge([8],[3]) = [3,8]

    merge([7],[4]) = [4,7]

    merge([2],[6]) = [2,6]

    merge([5],[1]) = [1,5]

  4. Combine: merge the results:

    merge([3,8],[4,7])

    • •compare 3 vs 4 → take 3
    • •compare 8 vs 4 → take 4
    • •compare 8 vs 7 → take 7
    • •append remaining 8

    Result: [3,4,7,8]

    merge([2,6],[1,5])

    • •compare 2 vs 1 → take 1
    • •compare 2 vs 5 → take 2
    • •compare 6 vs 5 → take 5
    • •append remaining 6

    Result: [1,2,5,6]

  5. Final combine:

    merge([3,4,7,8],[1,2,5,6])

    • •3 vs 1 → 1
    • •3 vs 2 → 2
    • •3 vs 5 → 3
    • •4 vs 5 → 4
    • •7 vs 5 → 5
    • •7 vs 6 → 6
    • •append remaining 7,8

    Result: [1,2,3,4,5,6,7,8]

Insight: Merge sort’s power comes from the fact that merging is linear and happens over log₂ n levels. Every element participates in one merge per level, giving Θ(n log n) time.

Quicksort: show how pivot choice changes the recursion #

Run one partition-based step on A = [1, 2, 3, 4, 5]. Compare choosing pivot = 1 (worst-ish) vs pivot = 3 (balanced). Use this to write the recurrence shape.

  1. If pivot p = 1:

    Partition result is:

    left = []

    pivot = [1]

    right = [2,3,4,5]

    So the recursive sizes are 0 and 4.

    Recurrence shape:

    T(5) = T(0) + T(4) + O(5)

    More generally (for sorted input and always-pick-first):

    T(n) = T(n−1) + O(n)

  2. If pivot p = 3:

    Partition result is:

    left = [1,2]

    pivot = [3]

    right = [4,5]

    Recursive sizes are 2 and 2.

    Recurrence shape:

    T(5) = T(2) + T(2) + O(5)

    More generally (balanced splits):

    T(n) = 2T(n/2) + O(n)

  3. Relate to asymptotics:

    Balanced: 2T(n/2)+O(n) ⇒ O(n log n)

    Unbalanced: T(n−1)+O(n) ⇒ O(n²)

Insight: Quicksort’s combine is essentially trivial, but its divide step (partition) must produce reasonably balanced subproblems to achieve O(n log n). Pivot strategy is therefore an algorithmic design decision, not an implementation detail.

Key Takeaways #

Common Mistakes #

Practice #

medium

You design an algorithm that splits a size-n problem into 3 subproblems of size n/2 and then spends O(n) time combining. Write the recurrence and give the asymptotic runtime.

Hint: Think about the recursion tree: how many total elements are processed per level, and how many levels are there?

Show solution

Recurrence:

T(n) = 3T(n/2) + O(n).

In a recursion tree, level i has 3^i subproblems of size n/2^i. If combine per subproblem is proportional to its size, total combine per level is:

3^i · (n/2^i) = n · (3/2)^i.

This grows geometrically with i, so the bottom levels dominate.

Depth is about log₂ n, so the last level has i = log₂ n:

Total ≈ n · (3/2)^{log₂ n}.

Use a^{log_b n} = n^{log_b a}:

(3/2)^{log₂ n} = n^{log₂(3/2)}.

So total is Θ(n · n^{log₂(3/2)}) = Θ(n^{1 + log₂(3/2)}) = Θ(n^{log₂ 3}).

Therefore T(n) = Θ(n^{log₂ 3}) (about Θ(n^{1.585})).

easy

Show that the recurrence T(n) = 2T(n/2) + n² is Θ(n²).

Hint: Compare work per level: does it stay constant like n, or change with level?

Show solution

At level 0, non-recursive work is n².

At level 1, there are 2 subproblems of size n/2, each costing (n/2)², so total is:

2 · (n²/4) = n²/2.

At level 2:

4 · (n/4)² = 4 · (n²/16) = n²/4.

So level i costs n² / 2^i.

Sum over i = 0 to log₂ n:

∑_{i=0}^{log₂ n} n²/2^i ≤ ∑_{i=0}^{∞} n²/2^i = 2n².

So total is O(n²). Also the first level alone costs n², so it is Ω(n²).

Therefore T(n) = Θ(n²).

hard

Consider quicksort with a pivot that always ends up splitting into sizes 1 and n−2 (ignoring the pivot itself). Write a recurrence and solve it to Θ(·).

Hint: This is still essentially a linear chain like T(n) = T(n−1) + O(n). Unroll it into a sum.

Show solution

Recurrence:

T(n) = T(1) + T(n−2) + O(n).

Since T(1) is constant, this behaves like:

T(n) = T(n−2) + cn.

Unroll:

T(n) = T(n−2) + cn

= T(n−4) + c(n−2) + cn

= T(n−6) + c(n−4) + c(n−2) + cn

Continue until the argument reaches 1 (about n/2 steps). The sum is roughly:

cn + c(n−2) + c(n−4) + ...

This is an arithmetic series with about n/2 terms and average term about n/2, so total is Θ(n²).

Therefore T(n) = Θ(n²).

Connections #

Quality: A (4.6/5)

← back to treebrowse all →