Divide and Conquer

Tags: #◇CCDSALG #◇Algorithms #◇Computer Science #◇Computational Complexity #◇Efficiency #◇Algorithm Design Paradigms #◇Recursion #◇Recursion and Iteration #◇Analysis of Algorithms #◇Data Structures #◇Time Complexity #◇Space Complexity

◇Overview

Divide and Conquer is an algorithm design paradigm that breaks a problem into smaller subproblems, solves them recursively, and combines the results.

◇Key Concepts

Three steps: Divide, Conquer, Combine Produces recurrence relations Classic examples: Merge Sort, Quick Sort, Binary Search Analyzed using ◇Master Theorem, ◇Recursion Tree Method, or ◇Substitution Method

◇Details / Theory

The Three Steps

Divide — Break the problem into smaller subproblems of the same type.
Conquer — Solve each subproblem recursively. If the subproblem size is small enough, solve it directly (base case).
Combine — Merge the subproblem solutions to form the solution to the original problem.

General Recurrence Form

A divide-and-conquer algorithm that divides the problem into $a$ subproblems, each of size $n/b$ , with $f(n)$ work to divide and combine, gives:
$T(n) = aT\left(\frac{n}{b}\right) + f(n)$

This is exactly the form handled by the ◇Master Theorem.

Classic Examples

Algorithm	Divide	Conquer	Combine	Recurrence	Result
Merge Sort	Split array in half	Sort each half	Merge sorted halves	$T(n) = 2T(n/2) + n$	$O(n \log n)$
Binary Search	Pick middle element	Search one half	None	$T(n) = T(n/2) + 1$	$O(\log n)$
Quick Sort	Partition around pivot	Sort each partition	None	Avg: $T(n) = 2T(n/2) + n$	Avg: $O(n \log n)$
Strassen’s Matrix Mult.	Divide into submatrices	7 recursive multiplications	Add/subtract results	$T(n) = 7T(n/2) + n^2$	$O(n^{2.81})$

When to Use Divide and Conquer

The problem can be naturally broken into independent subproblems of the same type. The subproblems are at most a constant fraction of the original size. The combine step is efficient (often $O(n)$ or $O(1)$ ).

Advantages

Often achieves optimal or near-optimal time complexity. Naturally suited for parallel execution (subproblems are independent). Leads to elegant, modular code.

Disadvantages

Recursive overhead (function call stack). Some problems have overlapping subproblems — for those, Dynamic Programming is more appropriate.

◇Common Pitfalls

Forgetting the base case, leading to infinite recursion. Using divide and conquer when subproblems overlap (use DP instead). Not accounting for the combine step’s cost in the recurrence.

◇Summary

TL;DR — Divide and Conquer splits a problem into smaller subproblems, solves them recursively, and combines results. It produces recurrences solvable by the Master Theorem and powers algorithms like Merge Sort and Binary Search.

◇Links

Related: ◇Master Theorem — ◇Recursion Tree Method — ◇Substitution Method — ◇Algorithm — ◇Recursion Source / Reference: Handout 01

Previous Topic: ◇Declarations
Next Topic: ◇Efficiency
Related Notes: ◇Master Theorem, ◇Recurrences

DIVIDE AND CONQUER