Divide and Conquer

Algorithms
strategy

Also known as: divide and solve

Grade 9-12

View on concept map

Divide and conquer is an algorithmic strategy that splits a problem into smaller subproblems of the same kind, solves those smaller problems, and then combines their solutions into one final answer. Many of the fastest algorithms in computer science use divide and conquer.

Definition

Divide and conquer is an algorithmic strategy that splits a problem into smaller subproblems of the same kind, solves those smaller problems, and then combines their solutions into one final answer. It is a structured form of decomposition often paired with recursion.

💡 Intuition

Break a big hard task into smaller versions of the same task, solve each one, then stitch the answers together.

🎯 Core Idea

The same solving pattern repeats on smaller pieces until the pieces are easy enough to solve directly.

Example

Merge sort splits a list into halves, sorts each half recursively, and then merges the sorted halves back together.

Formula

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

🌟 Why It Matters

Many of the fastest algorithms in computer science use divide and conquer. It helps students understand recursion, efficient sorting, and the structure of complex algorithms.

💭 Hint When Stuck

First define the base case. Then decide how the problem splits into smaller copies of itself. Finally, describe exactly how the smaller answers will be combined.

Formal View

A divide-and-conquer algorithm recursively solves subproblems and is often modeled by a recurrence of the form T(n) = aT(n/b) + f(n), where a subproblems of size n/b are combined with extra work f(n).

🚧 Common Stuck Point

You still need a clear combine step. Splitting a problem is not enough if you cannot reconstruct the final answer.

⚠️ Common Mistakes

  • Splitting the problem without reducing its size enough to reach a base case
  • Forgetting the combine step after the recursive calls finish
  • Using divide and conquer when the subproblems are not actually similar to the original problem

Common Mistakes Guides

Recursion

Frequently Asked Questions

What is Divide and Conquer in CS Thinking?

Divide and conquer is an algorithmic strategy that splits a problem into smaller subproblems of the same kind, solves those smaller problems, and then combines their solutions into one final answer. It is a structured form of decomposition often paired with recursion.

What is the Divide and Conquer formula?

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

When do you use Divide and Conquer?

First define the base case. Then decide how the problem splits into smaller copies of itself. Finally, describe exactly how the smaller answers will be combined.

How Divide and Conquer Connects to Other Ideas

To understand divide and conquer, you should first be comfortable with decomposition and recursion. Once you have a solid grasp of divide and conquer, you can move on to merge sort and efficiency.

← Back to Explorer