Ugenz Academy/Tutorial

Divideandconquer

9 min read1,768 words

Reading progress

Keep learning

Divide and Conquer

Divide and Conquer is an important algorithmic technique where we solve a big problem by breaking it into smaller problems, solving those smaller problems, and then combining their results.

It is closely connected to recursion.

1. What is Divide and Conquer?

The basic idea is:

Big Problem ↓ Divide ↓ Smaller Problems ↓ Conquer ↓ Solve Smaller Problems ↓ Combine ↓ Final Answer

There are three main steps:

1. Divide

Break the problem into smaller subproblems.

2. Conquer

Solve each smaller subproblem, usually using recursion.

3. Combine

Combine the solutions of the smaller problems to get the final answer.

2. Simple Real-Life Example

Suppose you have 1000 books and want to find a particular book.

Instead of checking all 1000 one by one:

1000 books ↓ Divide into 500 + 500 ↓ Choose the half where the book can be ↓ 500 ↓ 250 + 250 ↓ 125 + 125 ↓ ... ↓ 1 book

This idea is used by Binary Search.

3. Divide and Conquer Structure

A general recursive structure looks like:

solve(problem) { if (problem is small) { return direct_answer; } divide problem; solve(left_problem); solve(right_problem); combine results; }

The important thing is that the function keeps calling itself on smaller inputs.

4. Example: Binary Search

Binary Search is one of the simplest examples of Divide and Conquer.

Suppose:

[10, 20, 30, 40, 50, 60, 70]

We want to find 60.

First check the middle:

[10, 20, 30, 40, 50, 60, 70] ↑ 40

60 > 40, so we don't need the left half.

[50, 60, 70]

Again:

[50, 60, 70] ↑ 60

Found!

C++ Code

#include <iostream> #include <vector> using namespace std; int binarySearch(vector<int>& arr, int left, int right, int target) { if (left > right) return -1; int mid = left + (right - left) / 2; if (arr[mid] == target) return mid; if (target < arr[mid]) return binarySearch(arr, left, mid - 1, target); return binarySearch(arr, mid + 1, right, target); } int main() { vector<int> arr = {10, 20, 30, 40, 50, 60, 70}; int index = binarySearch(arr, 0, arr.size() - 1, 60); cout << index; return 0; }

Complexity

Each step cuts the problem approximately in half:

n n/2 n/4 n/8 n/16 ... 1

Therefore:

Time: O(log n)
Recursive space: O(log n)

5. Merge Sort

Merge Sort is one of the most important Divide and Conquer algorithms.

It follows all three steps clearly:

Divide Conquer Combine

Suppose:

[38, 27, 43, 3, 9, 82, 10]

Step 1 — Divide

[38 27 43 3 9 82 10] / \ [38 27 43] [3 9 82 10] / \ / \ [38] [27 43] [3 9] [82 10]

Keep dividing until each part has one element.

[38] [27] [43] [3] [9] [82] [10]

6. Conquer

Now recursively solve the smaller arrays.

For example:

[27] + [43] ↓ [27, 43]

And:

[38] + [27,43] ↓ [27,38,43]

7. Combine

Finally, merge the sorted parts.

[27, 38, 43] [3, 9, 10, 82] \ / \ / \ / [3, 9, 10, 27, 38, 43, 82]

8. Merge Sort C++ Implementation

#include <iostream> #include <vector> using namespace std; void merge(vector<int>& arr, int left, int mid, int right) { vector<int> temp; int i = left; int j = mid + 1; while (i <= mid && j <= right) { if (arr[i] <= arr[j]) { temp.push_back(arr[i]); i++; } else { temp.push_back(arr[j]); j++; } } while (i <= mid) { temp.push_back(arr[i]); i++; } while (j <= right) { temp.push_back(arr[j]); j++; } for (int k = 0; k < temp.size(); k++) { arr[left + k] = temp[k]; } } void mergeSort(vector<int>& arr, int left, int right) { if (left >= right) return; int mid = left + (right - left) / 2; // Divide mergeSort(arr, left, mid); mergeSort(arr, mid + 1, right); // Combine merge(arr, left, mid, right); } int main() { vector<int> arr = {38, 27, 43, 3, 9, 82, 10}; mergeSort(arr, 0, arr.size() - 1); for (int x : arr) { cout << x << " "; } return 0; }

Output:

3 9 10 27 38 43 82

9. Why is Merge Sort O(n log n)?

At each level, the array is divided into smaller parts.

Level 0: n ↓ Level 1: n/2 + n/2 ↓ Level 2: n/4 + n/4 + n/4 + n/4 ↓ ...

The number of levels is:

log₂(n)

At every level, merging all elements requires:

O(n)

Therefore:

O(n) × O(log n) ↓ O(n log n)

So:

Best: O(n log n)
Average: O(n log n)
Worst: O(n log n)
Extra Space: O(n)

10. Quick Sort

Quick Sort is another famous Divide and Conquer algorithm.

Instead of splitting exactly in half, it chooses a pivot.

Example:

[8, 3, 1, 7, 0, 10, 2]

Suppose pivot = 7.

Partition:

Smaller than 7 Pivot Greater than 7 [3,1,0,2] 7 [8,10]

Then recursively sort both sides:

[3,1,0,2] 7 [8,10] ↓ ↓ [0,1,2,3] 7 [8,10]

Final:

[0,1,2,3,7,8,10]

Quick Sort therefore follows:

Choose Pivot ↓ Partition ↓ Sort Left ↓ Sort Right

Average complexity:

O(n log n)

Worst case:

O(n²)

The worst case can happen when pivot selection repeatedly creates very unbalanced partitions.

11. Divide and Conquer Recurrence

This is an important concept for DSA.

For Merge Sort:

T(n) = 2T(n/2) + O(n)

Why?

There are:

2 smaller problems

Each has size:

n/2

And merging takes:

O(n)

Therefore:

T(n) = 2T(n/2) + O(n)

Result:

T(n) = O(n log n)

12. Binary Search Recurrence

Binary Search has only one smaller problem:

T(n) = T(n/2) + O(1)

Therefore:

T(n) = O(log n)

13. Common Divide and Conquer Algorithms

Some important examples are:

AlgorithmComplexity
Binary SearchO(log n)
Merge SortO(n log n)
Quick SortO(n log n) average
Maximum SubarrayO(n log n) divide-and-conquer approach
Closest Pair of PointsO(n log n)
Strassen Matrix Multiplication~O(n².81)
Fast ExponentiationO(log n)

14. Divide and Conquer vs Recursion

They are related but not the same thing.

Recursion

A function calls itself.

function ↓ function ↓ function

Divide and Conquer

A problem is divided into smaller problems and solved recursively.

Problem / \ Problem Problem / \ / \ ... ... ... ...

So:

Divide and Conquer commonly uses recursion, but recursion itself does not necessarily mean Divide and Conquer.

For example, factorial is recursive:

factorial(n) ↓ factorial(n-1) ↓ factorial(n-2)

But it isn't really a Divide and Conquer algorithm because it doesn't divide the problem into multiple independent subproblems.

15. Divide and Conquer vs Greedy

You just studied Greedy, so this difference is important.

FeatureDivide & ConquerGreedy
Main ideaBreak problemMake best current choice
Uses recursionUsuallyNot necessarily
Solves subproblemsYesUsually no
Reconsiders choicesNot the main ideaNo
ExampleMerge SortActivity Selection
ExampleBinary SearchFractional Knapsack
ExampleQuick SortDijkstra

Mental model

Divide and Conquer:

Big problem ↓ Break it ↓ Solve smaller problems ↓ Combine

Greedy:

Problem ↓ Best choice now ↓ Commit ↓ Best choice now ↓ Commit

16. Divide and Conquer vs Dynamic Programming

This is also important because Dynamic Programming comes later in your roadmap.

Divide and Conquer

Usually solves independent subproblems.

Problem / \ A B

A and B don't significantly overlap.

Dynamic Programming

Often has overlapping subproblems.

Problem / \ A B \ / C

The same subproblem may be needed multiple times.

DP stores previous results to avoid repeated work.

17. Advantages

1. Efficient algorithms

Many efficient algorithms use Divide and Conquer.

For example:

Binary Search → O(log n) Merge Sort → O(n log n)

2. Easier problem decomposition

A large problem becomes smaller and easier to understand.

3. Naturally works with recursion

The recursive structure often matches the problem structure.

4. Can support parallel processing

Independent subproblems can sometimes be processed simultaneously.

18. Disadvantages

1. Recursion overhead

Recursive calls require stack memory.

2. Extra memory

Some algorithms such as Merge Sort require additional memory.

3. Combining can be expensive

The divide step may be easy, but combining results can require significant work.

4. Not every problem fits

Some problems are better solved using:

  • Greedy
  • Dynamic Programming
  • Backtracking
  • Hashing
  • Graph algorithms

19. How to Identify Divide and Conquer

When solving a problem, ask:

Can I divide the problem? ↓ Can I solve each smaller part independently? ↓ Can I combine their answers? ↓ YES ↓ Divide and Conquer may work

Look for phrases such as:

  • Divide into two halves
  • Solve independently
  • Recursively solve
  • Merge results
  • Partition
  • Reduce problem size
  • Split into subproblems

20. The Most Important Pattern

Remember this:

PROBLEM │ DIVIDE / \ SUBPROBLEM SUBPROBLEM │ │ CONQUER CONQUER │ │ └─────┬──────┘ │ COMBINE │ ANSWER

Examples

Binary Search ↓ Divide search space ↓ Search one half ↓ Answer
Merge Sort ↓ Divide array ↓ Sort both halves ↓ Merge ↓ Sorted array
Quick Sort ↓ Choose pivot ↓ Partition ↓ Sort both sides ↓ Final sorted array

Final Summary

Divide and Conquer = Divide + Conquer + Combine

  • Divide: break a large problem into smaller problems.
  • Conquer: recursively solve the smaller problems.
  • Combine: use their results to create the final answer.
  • It is strongly connected to recursion.
  • Binary Search → O(log n)
  • Merge Sort → O(n log n)
  • Quick Sort → O(n log n) average, O(n²) worst
  • Merge Sort uses extra O(n) space.
  • Divide and Conquer is different from Greedy, Backtracking, and Dynamic Programming.

Keep learning. Keep building. Keep growing.

© 2026 Ugenz Academy