Divide and Conquer

Understand divide and conquer algorithms in Python: split, solve and combine, with counting inversions, quickselect, fast power and the Master Theorem.

• Intermediate
• 17 min read
• 4 objectives

Before this lessonLesson 5: Recursion

Divide and conquer is a way of designing algorithms, not a single algorithm. You divide a problem into smaller pieces of the same kind, conquer each piece recursively, and combine the answers. You have already met two examples: binary search (divide in half, keep one side) and merge sort (divide in half, sort both, merge). This lesson makes the pattern explicit and shows how to predict its running time.

The reason it is so effective is that halving is powerful. A problem of size one million only needs about 20 levels of halving to reach size one. If each level does linear work in total, the whole thing is O(n log n), which is dramatically faster than the O(n²) brute force for most problems.

The three steps

• Base case: a problem small enough to answer directly (often size 0 or 1).
• Divide: split into subproblems, usually two halves.
• Combine: merge the sub-answers into the answer for the whole. This step is where the cleverness lives.

Here is the simplest possible example: finding the maximum of a list by splitting it. It is not faster than a loop, but it shows the shape clearly.

def max_dc(nums, lo, hi):
    if lo == hi:                     # base case: one element
        return nums[lo]
    mid = (lo + hi) // 2
    left = max_dc(nums, lo, mid)     # conquer left half
    right = max_dc(nums, mid + 1, hi)
    return max(left, right)          # combine

orders = [14, 3, 27, 8, 19, 22, 5]
print(max_dc(orders, 0, len(orders) - 1))

27

Measuring cost with recurrences

Divide and conquer running times are written as a recurrence: the cost of size n in terms of the cost of smaller sizes. For merge sort, sorting n items means two sorts of n/2 plus O(n) merging: T(n) = 2T(n/2) + O(n). The Master Theorem gives the answer for recurrences of the form T(n) = a T(n/b) + O(nd), where a is the number of subproblems, b the shrink factor and d the exponent of the combine work:

• If d > logb a: the combine step dominates, T(n) = O(nd).
• If d = logb a: every level costs the same, T(n) = O(nd log n). Merge sort: a=2, b=2, d=1, so O(n log n).
• If d < logb a: the leaves dominate, T(n) = O(nlogb a).

Binary search is a=1, b=2, d=0, which falls in the middle case: O(log n). You do not need to memorise proofs; knowing these three cases lets you estimate almost any recursive split in an interview.

Counting inversions: a smarter combine step

An inversion is a pair i < j with a[i] > a[j]. It measures how unsorted a list is, and recommendation systems use it to compare two people's rankings. Checking every pair is O(n²). Instead, piggyback on merge sort: while merging two sorted halves, whenever you take an element from the right half, it is smaller than every element still waiting in the left half, so all of those form inversions at once.

def sort_and_count(a):
    if len(a) <= 1:
        return a, 0
    mid = len(a) // 2
    left, inv_l = sort_and_count(a[:mid])
    right, inv_r = sort_and_count(a[mid:])
    merged, inv = [], inv_l + inv_r
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            merged.append(left[i]); i += 1
        else:
            merged.append(right[j]); j += 1
            inv += len(left) - i         # all remaining left items are bigger
    merged += left[i:] + right[j:]
    return merged, inv

ranking = [3, 1, 5, 2, 4]
print(sort_and_count(ranking))
print(sort_and_count(list(range(10, 0, -1)))[1])

([1, 2, 3, 4, 5], 4)
45

A fully reversed list of 10 items has 10*9/2 = 45 inversions, which matches. Same recurrence as merge sort: time O(n log n), space O(n) for the merged lists.

Quickselect: the k-th smallest in average O(n)

To find the median, you could sort (O(n log n)). Quickselect is quicksort's lazy cousin: partition around a pivot, then recurse into only the side that contains position k. On average the sizes go n, n/2, n/4, ..., which sums to about 2n.

import random

def quickselect(nums, k):
    # k is 0-based: k=0 gives the smallest
    pivot = random.choice(nums)
    lows = [x for x in nums if x < pivot]
    pivots = [x for x in nums if x == pivot]
    highs = [x for x in nums if x > pivot]
    if k < len(lows):
        return quickselect(lows, k)
    if k < len(lows) + len(pivots):
        return pivot
    return quickselect(highs, k - len(lows) - len(pivots))

latencies = [120, 45, 300, 88, 45, 210, 97, 150, 60]
print("median:", quickselect(latencies, len(latencies) // 2))
print("3rd smallest:", quickselect(latencies, 2))

median: 97
3rd smallest: 60

Average time O(n), worst case O(n²) if pivots are always terrible; random pivots make that astronomically unlikely. This version uses O(n) extra space for clarity; an in-place partition brings it to O(1) plus recursion. In real Python code, heapq.nsmallest or statistics.median are the practical choices.

Fast exponentiation

Computing xⁿ by multiplying n times is O(n). But xⁿ = (x^n/2)², so you only need to solve one half-size problem and square it. That is a=1, b=2, d=0: O(log n). This is how cryptography computes huge powers modulo a prime.

def power(x, n, mod):
    if n == 0:
        return 1
    half = power(x, n // 2, mod)
    result = half * half % mod
    if n % 2 == 1:
        result = result * x % mod
    return result

print(power(3, 13, 1000))
print(power(2, 10**18, 1_000_000_007) == pow(2, 10**18, 1_000_000_007))

323
True

Python's built-in three-argument pow(x, n, mod) does exactly this, and you should use it in real code.

Recap

• Divide and conquer: base case, split into same-shaped subproblems, combine the results.
• Running time follows from a recurrence; the Master Theorem compares combine work with the number of subproblems.
• Counting inversions adds one line to merge sort's merge step and stays O(n log n).
• Quickselect recurses into one side only and averages O(n).
• Fast power halves the exponent each call, giving O(log n) multiplications.

# Write your solution here