Skip to content
Tutorials Center
My learning

Topics

Lesson 62 of 225 ยท Recursion and Backtracking

Divide and Conquer

Learn divide and conquer in Python: split, solve and combine. Covers fast power, merge sort, counting inversions, closest pair and Karatsuba with complexity.

Some problems are too big to solve in one go, but become easy once you cut them in pieces. Divide and conquer is the strategy of doing exactly that: split the problem into smaller sub-problems of the same kind, solve each one (usually by recursion), and combine the answers. It is behind some of the fastest algorithms you will meet: merge sort, quicksort, binary search, fast exponentiation, and fast multiplication.

This lesson gives you the three-step template, then applies it to four problems: fast power, merge sort (as a preview of the full lesson), counting inversions, and the maximum of an array. It ends with an overview of two famous algorithms: closest pair of points and Karatsuba multiplication.

The three steps

TEXT
solve(problem):
    if problem is small:                 # base case
        return the direct answer
    parts = divide(problem)              # 1. DIVIDE into smaller sub-problems
    answers = [solve(p) for p in parts]  # 2. CONQUER each sub-problem recursively
    return combine(answers)              # 3. COMBINE into the final answer

Think of sorting a pile of 1,000 exam papers: split it into two piles of 500, give one to each friend, who split their pile again, and so on. Piles of one paper are already sorted. Then everyone merges their sorted piles back together on the way up.

TEXT
              [8 3 5 1]
             /         \
        [8 3]           [5 1]       <- divide
        /   \           /   \
      [8]   [3]       [5]   [1]     <- base case: one item is sorted
        \   /           \   /
        [3 8]           [1 5]       <- combine (merge)
             \         /
              [1 3 5 8]

The cost depends on three numbers: how many sub-problems (a), how much smaller each one is (n/b), and how much work dividing and combining takes (f(n)). That gives the recurrence T(n) = a*T(n/b) + f(n), solved in Recurrences and the Master Theorem.

Divide and conquer is not the same as dynamic programming. In divide and conquer the sub-problems are usually independent (no overlap). When sub-problems overlap, as in Fibonacci, caching is the better tool; see Dynamic Programming.

Example 1: fast power

Computing x**n by multiplying n times costs O(n). Divide and conquer notices that x**n = (x**(n/2))**2 when n is even, so one half-size computation is enough. If n is odd, we need one extra multiplication by x:

TEXT
2^10 = (2^5)^2
2^5  = (2^2)^2 * 2
2^2  = (2^1)^2
2^1  = (2^0)^2 * 2 = 2
Python Fast power

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Computing 2^10 takes only 6 multiplications and 3^100 takes 10, instead of the 9 and 99 of repeated multiplication. The exponent is halved at every step, so there are about logโ‚‚ n calls: time O(log n) multiplications, stack depth O(log n). The trick of storing half in a variable matters: writing fast_power(x, n//2) * fast_power(x, n//2) would make two calls and bring back O(n). The technique also works for modular arithmetic and matrices; see Fast Exponentiation and Matrix Power.

Example 2: merge sort (a preview)

Merge sort divides the list in half, sorts each half recursively, and merges two sorted lists into one by repeatedly taking the smaller front item.

Python Merge sort in divide and conquer form

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The work is on the combine step. Each level of the recursion tree merges n items in total, and there are about logโ‚‚ n levels (the list halves each time), so the time is O(n log n). The merge needs a new list, so the extra space is O(n). The full lesson, with in-place tricks and a stability discussion, is Merge Sort.

Example 3: counting inversions

An inversion is a pair of positions i < j with a[i] > a[j]: two items that are in the wrong order. The number of inversions measures how unsorted a list is (0 for sorted, n(n-1)/2 for reversed). It is used, for example, to compare two rankings.

Brute force: check every pair. That is O(nยฒ).

Python Inversions, brute force

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Better: piggyback on merge sort. When we merge two sorted halves, whenever we take an item from the right half before the remaining left items, that right item is smaller than all the left items still waiting. Each such step counts len(left) - i inversions at once, with no pair-by-pair checking:

TEXT
left  = [3, 6, 9]      right = [2, 7]
take 2 (right) -> 3 left items still waiting are bigger: +3 inversions
take 3 (left)
take 6 (left)
take 7 (right) -> 1 left item (9) is bigger: +1 inversion
take 9 (left)                                   total across halves: 4
Python Inversions in O(n log n)

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The outputs match the brute force (3 and 10). The recurrence is the same as merge sort, T(n) = 2T(n/2) + O(n), so O(n log n) time and O(n) space. This is a classic example of getting extra information while combining.

Example 4: maximum by splitting

Finding the maximum of a list is naturally a loop, but splitting it shows the template in its simplest form, and shows when divide and conquer gives no benefit:

Python Maximum by divide and conquer

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

It uses n - 1 = 7 comparisons, exactly like a plain loop: the recurrence T(n) = 2T(n/2) + O(1) solves to O(n). Splitting is only worth it when it saves work or enables parallelism; it never beats the loop here. (The lesson: divide and conquer is a tool, not a goal.)

Two famous examples (overview)

Closest pair of points

Given n points in the plane, which two are closest? Brute force checks all pairs: O(nยฒ). Divide and conquer sorts the points by x, splits them with a vertical line, finds the closest pair on each side (distance d is the smaller of the two), and then only has to check pairs that cross the line. The key insight: only points within distance d of the line matter, and in that narrow strip, each point needs to be compared with only a handful (at most 7) of its neighbours when the strip is sorted by y. The combine step is therefore O(n), and the total is O(n log n). See Computational Geometry Basics.

Karatsuba multiplication

Multiplying two n-digit numbers the school way takes O(nยฒ) digit operations. Split each number into a high and a low half, x = a*10^m + b and y = c*10^m + d. Then x*y = ac*10^(2m) + (ad + bc)*10^m + bd seems to need four half-size multiplications. Karatsuba noticed that ad + bc = (a+b)(c+d) - ac - bd, so three half-size multiplications are enough: T(n) = 3T(n/2) + O(n), which is about O(n^1.585). Python's built-in big-integer multiplication uses this idea for very large numbers.

Python Karatsuba multiplication

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

When does divide and conquer pay off?

Algorithm Divide Combine Time
Binary search into 1 half (keep one) nothing O(log n)
Fast power into 1 half one multiplication O(log n)
Merge sort 2 halves merge, O(n) O(n log n)
Quicksort partition around a pivot nothing O(n log n) average
Closest pair 2 halves by x scan the strip O(n log n)
Karatsuba 3 half-size products additions O(n^1.585)

It pays off when the combine step is cheap compared to the savings, and when sub-problems are independent (which also makes the algorithm easy to run in parallel).

Common mistakes

  • Sub-problems that are not smaller, for example a mid-point formula that can leave one half equal to the whole list (watch lo, hi and mid off-by-one errors).
  • Calling the same sub-problem twice instead of storing the result in a variable (fast power).
  • Slicing lists in every call, which adds O(n) copy cost. It is fine for merge sort (the merge is already O(n)), but use index ranges in places like the maximum example.
  • Overlapping sub-problems. If they overlap, add a cache.
  • Forgetting the base case for an empty or single-item input.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What are the three steps of divide and conquer?

    You divide the problem into smaller ones, conquer each recursively, and combine their answers into the final result.
  2. 2. How many multiplications does fast power need roughly, for exponent n?

    The exponent is halved at each step, so there are about logโ‚‚ n levels, each doing at most two multiplications.
  3. 3. Why is the merge-sort-based inversion counter O(n log n) while the brute force is O(nยฒ)?

    When a right item is taken before the remaining left items, all of them form inversions with it, so len(left) - i inversions are added in one step.
  4. 4. What is the complexity of merge sort?

    There are about logโ‚‚ n levels of halving, and each level merges n items in total.
  5. 5. Karatsuba is faster than schoolbook multiplication because it uses:

    The identity ad + bc = (a+b)(c+d) - ac - bd saves one recursive multiplication, which lowers the exponent from 2 to about 1.585.

Summary

  • Divide and conquer = divide, conquer (recursively), combine. Costs follow T(n) = a*T(n/b) + f(n).
  • Fast power halves the exponent and reuses one result: O(log n).
  • Merge sort and inversion counting do their real work while merging: O(n log n).
  • Independent sub-problems suit divide and conquer; overlapping ones suit caching or DP.
  • Closest pair and Karatsuba show that a clever combine step can beat the obvious O(nยฒ).
  • Splitting is not automatically faster: the maximum example still costs O(n).

Next: Backtracking