40 Algorithms Every Programmer Should Know

Understanding the divide-and-conquer strategy

One of the strategies is to find a way to divide a larger problem into smaller problems that can be solved independently of each other. The subsolutions produced by these subproblems are then combined to generate the overall solution of the problem. This is called the divide-and-conquer strategy.

Mathematically, if we are designing a solution for a problem (P) with n inputs that needs to process dataset d, we split the problem into k subproblems, P₁ to P_k. Each of the subproblems will process a partition of the dataset, d. Typically, we will have P₁ to P_k processing d₁ to d_k.

Let's look at a practical example.