Divide and Conquer Principles and Techniques

This article mainly explains the core idea and techniques of divide and conquer algorithms.

Divide and Conquer Algorithm and Divide and Conquer Idea are not the same. The following examples will make this clear.

Divide and Conquer Idea

Divide and conquer idea is a broad concept. In this tutorial, it is also called the idea of "breaking down problems".

The idea of divide and conquer is to break down a problem into smaller subproblems, solve each subproblem, and then merge the results to get the answer to the original problem. This is very common in recursive algorithms.

For example, the recursive way to solve the Fibonacci sequence breaks fib(n) into two subproblems, fib(n-1) and fib(n-2), then combines their answers:

int fib(int n) {
    // base case
    if (n == 0 || n == 1) {
        return n;
    }
    return fib(n - 1) + fib(n - 2);
}

A simple binary tree problem, such as counting the number of nodes in a binary tree:

// Given a binary tree, count how many nodes in the tree.
int count(TreeNode root) {
    // base case
    if (root == null) {
        return 0;
    }
    // count nodes of left subtree and right subtree
    int leftCount = count(root.left);
    int rightCount = count(root.right);

    // sum up nodes of left subtree, right subtree and current node
    return leftCount + rightCount + 1;
}

This solution also follows the divide-and-conquer approach: you break down the total number of nodes in the entire tree (the original problem) into the number of nodes in the left subtree and the right subtree (subproblems). You then recursively calculate the node counts for the left and right subtrees, and finally derive the total node count from these subproblem solutions.

For example, does Dynamic Programming fall under the divide-and-conquer paradigm?

Yes, because all dynamic programming algorithms decompose a large problem into smaller, structurally similar subproblems, combining the optimal solutions of these subproblems to solve the original problem. This process often includes special optimization techniques.

Many more examples can be cited. In fact, I have summarized in Binary Tree Mastery (Outline) that recursive algorithms follow two main approaches: traversal or problem decomposition (divide-and-conquer).

Traversal-based algorithms are typically represented by Backtracking Algorithms. Therefore, apart from backtracking, other recursive algorithms can be categorized under the problem decomposition approach (divide-and-conquer).

Given this, "divide-and-conquer" plays a significant role in recursive algorithms. When we talk about "divide-and-conquer algorithms," what do we specifically mean? Can we say that all the recursive algorithms mentioned above are "divide-and-conquer algorithms"? Actually, not quite.

Divide-and-Conquer Algorithms

Narrowly defined, divide-and-conquer algorithms are recursive algorithms that apply the divide-and-conquer principle, but they have one distinctive feature that the previously listed algorithms lack:

The time complexity after decomposing the problem is lower than solving it directly without decomposition.

Only algorithms with this characteristic are referred to as "divide-and-conquer algorithms".

The algorithms mentioned earlier inherently require decomposition for their solutions; there's no direct method to solve them otherwise. Hence, we say they use the divide-and-conquer principle but aren't classified as divide-and-conquer algorithms.

For instance, Bucket Sort divides an array into several buckets, sorts each bucket using insertion sort, and then merges the sorted buckets, reducing the time complexity to $O(n)$.

Directly using Insertion Sort has a complexity of $O(n^2)$. By decomposing the problem and applying insertion sort on each bucket, the overall complexity drops to $O(n)$. This qualifies as a divide-and-conquer algorithm.

So why does dividing and conquering reduce complexity? If all problems were solved using divide-and-conquer, would they always result in lower complexity?

Let’s delve deeper into when divide-and-conquer reduces complexity, when it doesn’t, and the underlying principles.

Ineffective Divide and Conquer

Effective Divide and Conquer

Summary