Divide and Conquer -Recurrences
Divide and Conquer and Recurrences
1. Introduction
Many real-world problems are difficult to solve directly because of their large size. A common strategy is to divide a large problem into smaller problems, solve the smaller problems independently, and combine their solutions to obtain the solution to the original problem.
This strategy is known as the Divide and Conquer paradigm.
It is one of the most powerful algorithm design techniques and forms the basis of many efficient algorithms.
Examples include:
- Merge Sort
- Quick Sort
- Binary Search
- Karatsuba Multiplication
- Strassen Matrix Multiplication
- Closest Pair of Points
- FFT (Fast Fourier Transform)
2. What is Divide and Conquer?
Divide and Conquer is an algorithm design technique in which a problem is solved recursively by breaking it into smaller subproblems of the same type.
Every Divide and Conquer algorithm consists of three basic steps:
Step 1: Divide
Divide the original problem into one or more smaller subproblems.
These subproblems are usually similar to the original problem but smaller in size.
Step 2: Conquer
Solve the smaller subproblems recursively.
If the subproblem becomes sufficiently small, solve it directly without further recursion.
This smallest problem is called the base case.
Step 3: Combine
Combine the solutions of the smaller subproblems to obtain the solution to the original problem.
General Structure
Problem of size n Divide ↓ ------------------------- | | | P1 P2 P3 Conquer ↓ Solve recursively Combine ↓ Final Solution
3. General Algorithm
DivideAndConquer(problem) if problem is small solve directly else Divide the problem Solve each subproblem recursively Combine the solutions
This recursive structure is common to almost all Divide and Conquer algorithms.
4. Why Divide and Conquer Works Well
Instead of solving one large problem,
Size = n
we solve several smaller problems
Size = n/2 or Size = n/3 or Size = n/k
Each recursive call reduces the problem size.
Eventually,
n ↓ n/2 ↓ n/4 ↓ n/8 ↓ ... ↓ 1
The recursion stops at the base case.
5. Examples of Divide and Conquer Algorithms
| Algorithm | Divide | Combine |
|---|---|---|
| Binary Search | Half of the array | No combine required |
| Merge Sort | Two equal halves | Merge sorted lists |
| Quick Sort | Partition array | No explicit combine |
| Strassen Matrix Multiplication | Four submatrices | Matrix addition |
| Closest Pair of Points | Divide by x-coordinate | Compare boundary points |
These algorithms differ only in how they divide and combine the problem.
6. Recursion Tree
Every Divide and Conquer algorithm naturally forms a recursion tree.
Example
Problem n n / \ n/2 n/2 / \ / \ n/4 n/4 n/4 n/4
Each node represents one recursive call.
The leaves represent the base cases.
The recursion tree is one of the methods used later to analyze running time.
7. Need for Analysis
When recursion is involved,
ordinary loop counting cannot be used.
Instead,
we express the running time using a mathematical equation called a recurrence relation.
8. What is a Recurrence?
A recurrence is an equation that defines a function in terms of its values on smaller inputs. In algorithm analysis, recurrences naturally describe the running time of recursive Divide and Conquer algorithms.
Example
T(n) = T(n−1)+1
means
Time for size n=Time for size n−1+ One extra unit of work.
Another example
T(n)=2T(n/2)+n
means
Two recursive calls +Linear work done outside recursion.
9. Why Recurrences are Important
Suppose we analyze Merge Sort.
At every recursive call,
- divide the array
- recursively sort two halves
- merge the two sorted halves
Instead of writing the total running time directly,
we write
T(n)=2T(n/2)+n
This recurrence completely describes the running time.
The next task is solving the recurrence.
10. General Form of Divide and Conquer Recurrence
Most Divide and Conquer algorithms can be written as
where
- a = number of recursive subproblems
- n/b = size of each subproblem
- f(n) = work done for dividing and combining
This is the most common recurrence encountered in algorithm analysis.
Meaning of Each Term
a
Number of recursive calls.
Example
Merge Sort
2 recursive calls
Therefore
a=2
b
Reduction factor.
If each recursive call handles half the input,
b=2
f(n)
Work performed outside recursion.
Examples
Divide Merge Partition Copy Matrix addition
11. Examples
Binary Search
T(n)=T(n/2)+1
Only one recursive call.
Merge Sort
T(n)=2T(n/2)+n
Two recursive calls
Linear merge.
Quick Sort (Best Case)
T(n)=2T(n/2)+n
Strassen Matrix Multiplication
T(n)=7T(n/2)+n²
Uses seven recursive multiplications instead of eight, with quadratic work for matrix additions.
12. Base Case
Every recurrence requires a stopping condition.
Example
T(1)=1
or
T(0)=1
Without a base case,
recursion never terminates.
13. Writing a Recurrence
To write a recurrence,
answer three questions.
Question 1
How many recursive calls are made?
Example
2
Question 2
What is the size of each recursive call?
Example
n/2
Question 3
How much work is done outside recursion?
Example
Merge=O(n)
Then
T(n)=2T(n/2)+n
14. Examples of Common Recurrences
| Recurrence | Example Algorithm |
|---|---|
| T(n)=T(n−1)+1 | Recursive Linear Search |
| T(n)=T(n/2)+1 | Binary Search |
| T(n)=2T(n/2)+n | Merge Sort |
| T(n)=2T(n/2)+1 | Simple recursion |
| T(n)=7T(n/2)+n² | Strassen Matrix Multiplication |
| T(n)=8T(n/2)+1 | Classical Divide-and-Conquer Matrix Multiplication |
| T(n)=T(n/3)+T(2n/3)+n | Unequal-sized Divide and Conquer |
| T(n)=T(n/5)+T(7n/10)+n | Median-of-Medians Selection Algorithm |
These examples illustrate that subproblems may have equal or unequal sizes, depending on the algorithm.
15. Solving Recurrences
After writing a recurrence,
we must determine its asymptotic running time.
Several mathematical techniques are available.
Method 1: Substitution Method
Idea
- Guess the answer.
- Prove the guess using mathematical induction.
Suitable for
- Almost any recurrence.
- Requires a correct guess.
Example
Guess
T(n)=O(n log n)
Then prove it by induction.
Method 2: Iteration Method
Idea
Expand the recurrence repeatedly until the base case is reached.
Example
T(n) ↓ 2T(n/2)+n ↓ 4T(n/4)+2n ↓ 8T(n/8)+3n
Continue until
n=1
This method reveals patterns and helps derive a closed-form solution.
Method 3: Recursion Tree Method
Idea
Represent the recurrence as a tree.
Compute
- cost at each level
- number of levels
- total cost
Very intuitive.
Useful for
Merge Sort
Quick Sort
Karatsuba
Many Divide and Conquer algorithms.
Method 4: Master Method (Master Theorem)
Most frequently used in algorithm analysis.
Applicable to recurrences of the form
Provides the asymptotic solution directly by comparing
This is one of the fastest methods when applicable.
16. Comparison of Methods
| Method | Basic Idea | Advantages | Limitations |
|---|---|---|---|
| Substitution | Guess and prove by induction | Very general | Requires a good guess and proof |
| Iteration | Expand repeatedly | Easy to understand | Can become lengthy |
| Recursion Tree | Sum costs level by level | Visual and intuitive | Less convenient for complex recurrences |
| Master Method | Apply theorem directly | Very fast | Applicable only to specific recurrence forms |
17. Flow of Analysis
Recursive Algorithm │ ▼ Write the Recurrence │ ▼ Choose a Solution Method │ ├── Substitution ├── Iteration ├── Recursion Tree └── Master Method │ ▼ Obtain Asymptotic Complexity
18. Summary
- Divide and Conquer solves a large problem by recursively dividing it into smaller subproblems, solving each one, and combining their solutions.
- Every Divide and Conquer algorithm has three phases: Divide, Conquer, and Combine.
- The running time of recursive algorithms is naturally expressed using recurrence relations.
-
A typical Divide and Conquer recurrence has the form:
- Recurrences are solved to determine the asymptotic time complexity of recursive algorithms.
-
The four major techniques for solving recurrences are:
- Substitution Method
- Iteration Method
- Recursion Tree Method
- Master Method
Comments
Post a Comment