Unit II

Divide and Conquer Algorithm

Easy-Language Notes with Examples

Topics Covered:

• What is Divide and Conquer?

• Binary Search

• Merge Sort

• Quick Sort

• Closest Pair of Points

• Strassen's Matrix Multiplication

• Cooley–Tukey FFT Algorithm

• Karatsuba Fast Multiplication

1. What is Divide and Conquer?
Divide and Conquer is a powerful algorithm design technique. It solves a big problem by breaking it into
smaller subproblems, solving each one separately, and then combining their answers to get the final
result.

🌟 Real-Life Example:

Imagine finding a name in a phone book. Instead of reading every page, you open the
middle.

If the name comes before the middle → search left half. Otherwise → search right half.

You keep halving the search space until you find the name. That's Divide and Conquer!

Three Steps of Divide and Conquer

• Step 1 — Divide: Break the original problem into smaller subproblems of the same type.
• Step 2 — Conquer: Solve each subproblem. If it is still large, apply Divide and Conquer again
(recursion).
• Step 3 — Combine (Merge): Combine the solutions of all subproblems to get the final answer.

Characteristics of Divide and Conquer

• Dividing the problem: The problem is split into k smaller subproblems (usually 2).
• Independence of subproblems: Each subproblem is solved on its own — they do not depend
on each other.
• Conquering each subproblem: Solve recursively. The recursion stops when the problem is
small enough to solve directly (base case).
• Combining solutions: Merge the results from subproblems into the final answer.

General Pseudocode (Control Abstraction)

DivideAndConquer(P):
if P is small enough:
return Solve(P) // base case — solve directly
Divide P into subproblems P1, P2, ..., Pk
for each subproblem Pi:
yi = DivideAndConquer(Pi) // solve recursively
return Combine(y1, y2, ..., yk) // merge answers

Applications of Divide and Conquer

• Binary Search — find an element in a sorted list
• Merge Sort — sort an array by splitting and merging
• Quick Sort — sort using a pivot element
• Closest Pair of Points — find the two closest points in a plane
• Strassen's Algorithm — multiply large matrices faster
• Cooley–Tukey FFT — fast frequency analysis of signals
• Karatsuba Algorithm — multiply large numbers faster
2. Binary Search
What is the Problem?
You have a sorted list of elements. You want to find out if a given value x exists in the list. If it does,
return its position. If not, return 0 (not found).

Key Condition: The list MUST be sorted before Binary Search can work.

Think of it like a dictionary — you know which half of the book to look in based on the first
letter.

How Binary Search Works (Divide and Conquer)

• Divide: Look at the middle element of the current list.
• Compare: Is the middle element equal to x? If yes, found! Is it greater? Search left half. Is it
smaller? Search right half.
• Conquer: Repeat on the chosen half.
• Base case: If the list becomes empty, x is not present.

Pseudocode
BinarySearch(a, low, high, x):
if low > high:
return 0 // not found
mid = (low + high) / 2
if a[mid] == x:
return mid // found at position mid
else if x < a[mid]:
return BinarySearch(a, low, mid-1, x) // search left half
else:
return BinarySearch(a, mid+1, high, x) // search right half

Dry Run Example

Sorted list: [-15, -6, 0, 7, 9, 23, 54, 82, 101, 112, 125, 131, 142, 151]
Search for x = 82 (14 elements, indices 1 to 14)

Step low high mid a[mid] Action

1 1 14 7 54 82 > 54 → search right half
2 8 14 11 125 82 < 125 → search left half
3 8 10 9 101 82 < 101 → search left half
 4 8 8 8 82 82 == 82 → FOUND at index 8!

Binary Search found 82 at index 8 in just 4 steps instead of scanning all 14 elements!

Internal vs External Nodes

• Internal nodes (circles): The element was found at that index.
• External nodes (squares): The element was not found (search ended in empty space).

⏱ Time Complexity 💾 Space Complexity

O(log n) O(log n) recursive / O(1)
iterative
Each step cuts the problem in half. So for n elements, we need at most log₂(n) steps. Space is O(log n)
because of the recursion stack (each call is stored until it returns).
3. Merge Sort
What is the Problem?
Given an unsorted array, sort it in ascending order. Merge Sort does this by splitting the array into
halves, sorting each half recursively, and then merging the two sorted halves back together.

🌟 Real-Life Example:

Imagine splitting a deck of cards into two halves, sorting each half separately,

then carefully merging both sorted halves into one sorted deck.

How Merge Sort Works

• Divide: Split the array into two halves from the middle.
• Conquer: Recursively sort the left half and right half.
• Combine: Merge the two sorted halves into one sorted array.

The Merge Step — How It Works

Two pointers h and j start at the beginning of each half. Compare a[h] and a[j]. Copy the smaller one
into a temporary array b[]. Move that pointer forward. Repeat until one half is fully copied. Copy the
remaining elements of the other half. Copy b[] back into the original array.

Pseudocode
MergeSort(a, low, high):
if low < high:
mid = (low + high) / 2
MergeSort(a, low, mid) // sort left half
MergeSort(a, mid+1, high) // sort right half
Merge(a, low, mid, high) // combine both halves

Merge(a, low, mid, high):

h = low, j = mid+1, i = low // three pointers
while h <= mid and j <= high:
if a[h] <= a[j]:
b[i] = a[h], h = h + 1
else:
b[i] = a[j], j = j + 1
i = i + 1
copy any remaining elements from left half into b[]
 copy any remaining elements from right half into b[]
copy b[low..high] back into a[low..high]

Example Trace
Input: [38, 27, 43, 3, 9, 82, 10]
• Split → [38, 27, 43, 3] and [9, 82, 10]
• Split left → [38, 27] and [43, 3] → [38] [27] → Merge → [27, 38]
• Split right → [43] [3] → Merge → [3, 43] → Merge with [27,38] → [3, 27, 38, 43]
• Right side [9, 82, 10] → [9] [82,10] → [9] [10,82] → Merge → [9, 10, 82]
• Final Merge: [3, 27, 38, 43] + [9, 10, 82] → [3, 9, 10, 27, 38, 43, 82]

⏱ Time Complexity 💾 Space Complexity

O(n log n) — all cases O(n)
The array is split log n times, and each merge step processes all n elements → O(n log n). Space is
O(n) for the temporary array b[].
4. Quick Sort
What is the Problem?
Sort an array in ascending order — just like Merge Sort. But Quick Sort does it differently: it picks a
special element called the pivot and rearranges elements around it. Elements smaller than pivot go left,
elements larger go right.

🌟 Real-Life Example:

Imagine lining up students by height. You pick one student as the 'pivot'.

Everyone shorter stands on the left, taller on the right.

Then you repeat this for each group until everyone is sorted!

How Quick Sort Works (Divide and Conquer)

• Divide: Choose a pivot (usually the last element). Partition the array — left side has elements ≤
pivot, right side has elements > pivot.
• Conquer: Recursively apply Quick Sort to the left part and right part.
• Combine: No extra work needed! The array is sorted in place during partitioning.

Pseudocode
QuickSort(A, low, high):
if low < high:
p = Partition(A, low, high) // find pivot position
QuickSort(A, low, p-1) // sort left of pivot
QuickSort(A, p+1, high) // sort right of pivot

Partition(A, low, high):

pivot = A[high] // last element is pivot
i = low - 1 // i tracks where next small element goes
for j = low to high-1:
if A[j] <= pivot:
i = i + 1
swap A[i] and A[j] // move small element to left side
swap A[i+1] and A[high] // place pivot in correct position
return i + 1 // return pivot index

Example Trace
Input: [10, 7, 8, 9, 1, 5] → Pivot = 5 (last element)
• Partition step: compare each element with 5.
• Elements ≤ 5: move to left. Result: [1, 5, 10, 7, 8, 9]. Pivot 5 is now at index 1.
• Left of 5: [1] → already sorted.
• Right of 5: [10, 7, 8, 9] → apply Quick Sort again → [7, 8, 9, 10].
• Final sorted array: [1, 5, 7, 8, 9, 10] ✔

Time Complexity — Three Cases

Case When It Happens Time Complexity
Best Case Pivot always divides array into two equal O(n log n)
halves
Average Case Pivot divides reasonably well on average O(n log n)
Worst Case Array is already sorted; pivot is always the O(n²)
smallest

⏱ Time Complexity 💾 Space Complexity

O(n log n) avg / O(n²) O(log n) avg / O(n) worst
worst
Space is used by the recursion stack. In the average case, the stack depth is log n. In the worst case
(already sorted array), the stack depth becomes n.

Merge Sort vs Quick Sort — Quick Comparison

Feature Merge Sort Quick Sort
Strategy Always splits equally Splits around pivot
Worst case O(n log n) O(n²)
Extra memory O(n) — needs temp array O(log n) — in-place
Stable sort? Yes No (depends on implementation)
Preferred for Linked lists, guaranteed speed Arrays, practical speed
5. Closest Pair of Points
What is the Problem?
Given a set of points in a 2D plane (each point has x and y coordinates), find the two points that are
closest to each other (minimum distance between any two points).

🌟 Real-Life Application:

Air Traffic Control — find the two aircraft that are closest to each other to prevent collision!

Why Not Brute Force?

Brute Force: Check every pair of points. For n points there are n×(n−1)/2 pairs → O(n²). This is too slow
for large datasets. Divide and Conquer reduces this to O(n log n).

Divide and Conquer Strategy

• Step 1 — Sort: Sort all points by their x-coordinate.
• Step 2 — Divide: Find the middle point. Split points into left half and right half.
• Step 3 — Conquer: Recursively find the closest pair in the left half (call the distance dL) and
the closest pair in the right half (call it dR).
• Step 4 — Combine (Strip): Let d = min(dL, dR). Now check if there is a closer pair with one
point on each side of the dividing line. Only look at points within distance d from the dividing line
(called the 'strip').
• Step 5 — Answer: Return the minimum distance found from both recursive calls and the strip
check.

Base Cases
• 1 point: No pair possible.
• 2 points: Only one pair — return its distance.
• 3 points: Check all 3 pairs and return the minimum.

Pseudocode
ClosestPair(points, n):
if n <= 3:
return BruteForce(points) // check all pairs directly
mid = n / 2
midPoint = points[mid]
dL = ClosestPair(points[0..mid], mid) // left half
dR = ClosestPair(points[mid..n], n-mid) // right half
d = min(dL, dR)
 strip = all points with x within d of midPoint.x
dStrip = ClosestInStrip(strip, d)
return min(d, dStrip)

Worked Example
Given 6 points:
Point x y
P1 2 3
P2 12 30
P3 40 50
P4 5 1
P5 12 10
P6 3 4

Step 1: Sort by x: P1(2,3), P6(3,4), P4(5,1), P5(12,10), P2(12,30), P3(40,50)

Step 2: Split → Left: {P1, P6, P4} Right: {P5, P2, P3}
Step 3: Conquer:
• Left half distances: d(P1,P6) = √2 ≈ 1.41, d(P1,P4) ≈ 3.61, d(P6,P4) ≈ 3.61 → dL = 1.41
• Right half distances: d(P5,P2) = 20, d(P5,P3) ≈ 50, d(P2,P3) ≈ 34 → dR = 20
Step 4: d = min(1.41, 20) = 1.41. Check strip around dividing line x=5 for points within 1.41.

Final Answer: Minimum distance = 1.41 (between points P1(2,3) and P6(3,4))

⏱ Time Complexity 💾 Space Complexity

O(n log n) O(n log n)
Sorting: O(n log n). Each recursion level processes all n points (O(n) for the strip check). There are log
n levels → O(n log n) total. Space O(n log n) for pre-sorted arrays at each recursion level.
6. Strassen's Matrix Multiplication
What is the Problem?
Multiply two n×n matrices A and B to get matrix C = A × B. The classical (normal) method requires
O(n³) operations, which is very slow for large matrices. Strassen's algorithm does it faster using Divide
and Conquer.

Key Insight: For 2×2 blocks, the normal method needs 8 multiplications.

Strassen found a clever way to do it with only 7 multiplications.

Multiplications are costly! Fewer multiplications = faster algorithm.

How It Works — The Idea

• Step 1 — Divide: Split each n×n matrix into four (n/2)×(n/2) sub-matrices: A11, A12, A21, A22
and B11, B12, B21, B22.
• Step 2 — Conquer: Compute 7 special intermediate products (M1 through M7) using recursive
calls. These use clever sums and differences of sub-matrices instead of 8 direct multiplications.
• Step 3 — Combine: Compute the four blocks of C using additions and subtractions of M1–M7.

The 7 Intermediate Products (M1 to M7)

These are the 7 recursive multiplications Strassen uses:
Product Formula
M1 (A11 + A22) × (B11 + B22)
M2 (A21 + A22) × B11
M3 A11 × (B12 − B22)
M4 A22 × (B21 − B11)
M5 (A11 + A12) × B22
M6 (A21 − A11) × (B11 + B12)
M7 (A12 − A22) × (B21 + B22)

Final Combination Step

The four blocks of C are built from M1–M7 using only additions and subtractions:
• C11 = M1 + M4 − M5 + M7
• C12 = M3 + M5
• C21 = M2 + M4
• C22 = M1 − M2 + M3 + M6

Pseudocode
 Strassen(A, B, n):
if n == 1:
return A[1][1] × B[1][1] // base case
Partition A into A11, A12, A21, A22
Partition B into B11, B12, B21, B22
Compute M1 to M7 using recursive Strassen calls
C11 = M1 + M4 - M5 + M7
C12 = M3 + M5
C21 = M2 + M4
C22 = M1 - M2 + M3 + M6
return combined matrix C

Method Multiplications Time Complexity

Classical (Normal) 8 per block O(n³)
Strassen's 7 per block O(n^2.81)

⏱ Time Complexity 💾 Space Complexity

O(n^2.81) O(n²)
Strassen uses only 7 recursive multiplications instead of 8. By the Master Theorem this gives
O(n^log₂7) ≈ O(n^2.81). Much faster than O(n³) for large matrices.

When to Use / When Not to Use

• Good for: Very large matrices where multiplication cost dominates.
• Not ideal for: Small matrices (overhead of all the additions outweighs the benefit). Also uses
more memory and can have minor floating-point accuracy issues.
7. Cooley–Tukey FFT Algorithm
What is the Problem?
Computing the Discrete Fourier Transform (DFT) of a signal converts it from the time domain to the
frequency domain. This tells you what frequencies (tones) are present in a signal. The direct method to
compute DFT is slow: O(N²). The Cooley–Tukey FFT (Fast Fourier Transform) reduces this to O(N log
N) using Divide and Conquer.

🌟 Real-Life Use:

Every time you listen to an MP3 song, FFT is used to compress the audio!

FFT is also used in medical imaging (MRI), radar, WiFi, and phone signals.

Key Idea — Divide and Conquer on a Signal

Instead of computing the DFT of the whole signal at once, we split the input into two halves:
• Even-indexed elements: x₀, x₂, x₄, x₆, ...
• Odd-indexed elements: x₁, x₃, x₅, x₇, ...
Recursively compute the FFT of each half. Combine the results using a special complex number called
the twiddle factor. This halving continues until we reach size-1 sequences (base case).

Step-by-Step Explanation
• Step 1 — Divide: Split input [x₀, x₁, x₂, x₃, x₄, x₅, x₆, x₇] into even part [x₀, x₂, x₄, x₆] and odd
part [x₁, x₃, x₅, x₇].
• Step 2 — Conquer: Recursively apply FFT on even part → Xe. Recursively apply FFT on odd
part → Xo.
• Step 3 — Combine: For each k from 0 to N/2 − 1, use a twiddle factor w = e^(−j·2π·k/N) to
combine: X[k] = Xe[k] + w × Xo[k] and X[k + N/2] = Xe[k] − w × Xo[k].

Pseudocode
FFT(x):
n = length of x
if n == 1:
return x // base case
xe = elements at even indices of x
xo = elements at odd indices of x
Xe = FFT(xe) // conquer left
Xo = FFT(xo) // conquer right
for k = 0 to (n/2 - 1):
w = e^(-j * 2π * k / n) // twiddle factor
 X[k] = Xe[k] + w × Xo[k]
X[k + n/2] = Xe[k] - w × Xo[k]
return X

Method Time Complexity

Direct DFT (no FFT) O(N²)
Cooley–Tukey FFT O(N log N)

⏱ Time Complexity 💾 Space Complexity

O(N log N) O(N)
The signal is split log N times. Each level does O(N) work (combining). Total = O(N log N). Space O(N)
for storing intermediate results.

Where FFT is Used

• Audio/music compression — MP3 format
• Image processing — JPEG compression
• Wireless communications — WiFi, 4G/5G
• Medical imaging — MRI and CT scans
• Radar and sonar signal analysis
• Machine learning — feature extraction from audio/video
8. Karatsuba Algorithm for Fast Multiplication
What is the Problem?
Multiplying two very large numbers (with many digits) using the normal school method takes O(n²) time,
where n is the number of digits. The Karatsuba algorithm multiplies large integers faster using Divide
and Conquer — reducing the number of recursive multiplications from 4 to just 3.

🌟 Real-Life Use:

Used in cryptography (RSA encryption), scientific computing,

and big number libraries when numbers have thousands of digits.

Key Idea — Reduce 4 Multiplications to 3

Say we have two large numbers X and Y, each with n digits. We split each number into two halves:
• X = A × 10^(n/2) + B (A is the left/high half, B is the right/low half)
• Y = C × 10^(n/2) + D (C is the left/high half, D is the right/low half)

Normal multiplication of X × Y needs 4 recursive multiplications: AC, AD, BC, BD. Karatsuba's trick
reduces this to 3:
• p=A×C
• q=B×D
• r = (A + B) × (C + D)
Then: AD + BC = r − p − q (we get this for free without extra multiplications!)
Final result: X × Y = p × 10^n + (r − p − q) × 10^(n/2) + q

Step-by-Step Algorithm
• Step 1: If numbers are small (single digit), multiply directly.
• Step 2: Split both numbers into their top half (A, C) and bottom half (B, D).
• Step 3: Recursively compute p = A × C, q = B × D, r = (A+B) × (C+D).
• Step 4: Combine using the Karatsuba formula.

Pseudocode
Karatsuba(X, Y):
if X or Y is single digit:
return X × Y // base case
n = max(number of digits in X, Y)
half = n / 2
A = top half digits of X // high part of X
 B = bottom half digits of X // low part of X
C = top half digits of Y // high part of Y
D = bottom half digits of Y // low part of Y
p = Karatsuba(A, C) // recursive call 1
q = Karatsuba(B, D) // recursive call 2
r = Karatsuba(A+B, C+D) // recursive call 3
middle = r - p - q // AD + BC
return p × 10^(2×half) + middle × 10^half + q

Why This is Faster

Method Recursive Multiplications Time Complexity
Normal (school method) 4 per level O(n²)
Karatsuba Algorithm 3 per level O(n^1.585)

⏱ Time Complexity 💾 Space Complexity

O(n^1.585) O(n)
By the Master Theorem with 3 recursive calls on size n/2: T(n) = 3T(n/2) + O(n) → O(n^log₂3) ≈
O(n^1.585). Significantly faster than O(n²) for large numbers.

Simple Numerical Example

Multiply X = 12 and Y = 34 (for simplicity)
• A = 1, B = 2, C = 3, D = 4, half = 1
• p=A×C=1×3=3
• q=B×D=2×4=8
• r = (A+B) × (C+D) = (1+2) × (3+4) = 3 × 7 = 21
• middle = r − p − q = 21 − 3 − 8 = 10
• Result = p × 10² + middle × 10¹ + q = 300 + 100 + 8 = 408 ✔

12 × 34 = 408 — correct! And we only did 3 multiplications instead of 4.

Quick Revision — All Topics at a Glance
Topic Simple Meaning Time Complexity
Divide & Conquer Break problem → solve parts → combine Depends on
problem
Binary Search Search sorted list by halving each step O(log n)
Merge Sort Split array, sort halves, merge back O(n log n) always
Quick Sort Partition around pivot, sort both sides O(n log n) avg,
O(n²) worst
Closest Pair Split points, find min dist, check strip O(n log n)
Strassen's Matrix multiply with 7 multiplications instead O(n^2.81)
of 8
Cooley–Tukey FFT Split signal into even/odd, combine with O(N log N)
twiddle factor
Karatsuba Split number, do 3 recursive multiplications O(n^1.585)
instead of 4

Key Points to Remember

• Divide and Conquer = Divide → Conquer (recursively) → Combine.
• Binary Search: Array MUST be sorted. Cut search space in half each time. O(log n).
• Merge Sort: Always O(n log n) but needs extra O(n) space for temp array.
• Quick Sort: In-place, fast in practice, but worst case O(n²) if pivot is bad.
• Closest Pair: After finding dL and dR, always check the strip! Otherwise you'll miss cross-
boundary pairs.
• Strassen's: Saves 1 multiplication per recursion level. Useful only for very large matrices.
• FFT: Split into even/odd indexed elements. O(N log N) vs O(N²) for direct DFT.
• Karatsuba: 3 recursive calls instead of 4. Uses formula: middle = (A+B)(C+D) − AC − BD.

End of Unit II Notes