What are the three steps of divide and conquer?

Divide: split problem into subproblems. Conquer: recursively solve each subproblem (base case: solve directly). Combine: merge solutions of subproblems into overall solution.

Why is Strassen's algorithm faster than naive matrix multiplication?

Naive uses 8 recursive multiplications giving T(n)=8T(n/2)+O(n²)→O(n³). Strassen uses only 7 multiplications: T(n)=7T(n/2)+O(n²)→O(n^2.81) by Master theorem.

What is the time complexity of binary search?

O(log n). Recurrence: T(n)=T(n/2)+O(1) → by Master theorem Case 2 (p=0, f=Θ(1)): T(n)=Θ(log n).

How does the closest pair of points algorithm achieve O(n log n)?

Divide points by median x-coordinate. Solve each half recursively. The combine step checks strip of width 2δ around dividing line — at most 8 points to compare per point in the strip, giving O(n) combine. Recurrence: T(n)=2T(n/2)+O(n log n)=O(n log²n), or O(n log n) if pre-sort by y.

Divide & Conquer

Binary Search, Merge Sort, Quick Sort, Strassen, Karatsuba, and more — with recurrence analysis for GATE CS.

Last updated: April 2026 | GATE CS 2024–2026 syllabus

Key Takeaways

D&C: Divide into subproblems → Conquer recursively → Combine results.
Recurrence T(n)=aT(n/b)+f(n) → solve with Master theorem.
Binary search: T(n)=T(n/2)+1 → Θ(log n).
Merge sort: T(n)=2T(n/2)+n → Θ(n log n).
Strassen: T(n)=7T(n/2)+n² → Θ(n^log₂7) ≈ O(n^2.81).
Karatsuba: T(n)=3T(n/2)+n → Θ(n^log₂3) ≈ O(n^1.585).
D&C is optimal when subproblems are independent and combine is efficient.

1. The D&C Paradigm

Three phases:
1. Divide: Split problem of size n into a subproblems each of size n/b.
2. Conquer: Solve recursively. If size ≤ threshold, solve directly.
3. Combine: Merge solutions. Cost = f(n).

Recurrence: T(n) = aT(n/b) + f(n)
Apply Master theorem to find Θ.

Algorithm	a	b	f(n)	T(n)
Binary search	1	2	O(1)	Θ(log n)
Merge sort	2	2	O(n)	Θ(n log n)
Quick sort (avg)	2	2	O(n)	Θ(n log n)
Strassen	7	2	O(n²)	Θ(n^2.81)
Karatsuba	3	2	O(n)	Θ(n^1.585)

2. Binary Search

Search sorted array by comparing with the middle element and eliminating half.

Recurrence: T(n) = T(n/2) + O(1)
Master theorem: a=1, b=2, p=log₂1=0, f=O(1)=Θ(n⁰) → Case 2 → T(n)=Θ(log n)

Iterations: at most ⌊log₂n⌋+1
Comparisons: at most 2log₂n+1 (two comparisons per iteration: < and =)

Variations:
First occurrence of x: continue search left after finding x → O(log n)
Lower bound (first ≥x): standard binary search variant → O(log n)
Unbounded/exponential search: first find range 2^k, then binary search → O(log ans)

3. Merge Sort

T(n) = 2T(n/2) + Θ(n) → Θ(n log n)
Merge step: O(n) using two pointers on sorted halves
Total comparisons: between n⌊log n⌋ and n⌈log n⌉
Inversions counted: merge sort can count inversions in O(n log n) by counting right-side picks during merge.

Counting inversions: An inversion is (i,j) with i<j but A[i]>A[j]. During merge, whenever an element from the right half is picked before an element of the left half, add the count of remaining left elements to inversion count.

4. Quick Sort — Recurrence Analysis

Best/Average (balanced pivot): T(n) = 2T(n/2) + n → Θ(n log n)
Worst (always 1:n−1 split): T(n) = T(n−1) + n → Θ(n²)
Expected (random pivot): E[T(n)] = 2n ln n ≈ 1.386 n log₂n

k:1−k split (0<k<1): T(n) = T(kn)+T((1−k)n)+n
By recursion tree: depth = log_1/kn, each level costs n → Θ(n log n) for any fixed k.

5. Strassen Matrix Multiplication

Multiplying two n×n matrices. Naive: 8 multiplications of n/2×n/2 blocks.

Naive: T(n) = 8T(n/2) + O(n²) → a=8, p=log₂8=3, f=O(n²) → Case 1 → Θ(n³)

Strassen: T(n) = 7T(n/2) + O(n²) → a=7, p=log₂7≈2.807, f=O(n²) → Case 1
T(n) = Θ(n^log₂7) ≈ Θ(n^2.81)

Strassen computes 7 products M₁–M₇ using additions/subtractions to eliminate 1 multiplication.
Current best: Williams et al. ~O(n^2.37), not examinable in GATE.

6. Karatsuba Integer Multiplication

Multiply two n-digit integers. Split each into two n/2-digit halves.

Naive school multiplication: T(n) = 4T(n/2) + O(n) → Θ(n²)

Karatsuba trick: Need ac, bd, and (a+b)(c+d)−ac−bd = ad+bc. Only 3 multiplications!
T(n) = 3T(n/2) + O(n) → a=3, p=log₂3≈1.585, f=O(n) → Case 1
T(n) = Θ(n^log₂3) ≈ Θ(n^1.585)

7. Closest Pair of Points

Input: n points in 2D plane. Find pair with minimum Euclidean distance.

Algorithm:
1. Sort by x-coordinate: O(n log n)
2. Divide at median x. Let δ = min(dist in left, dist in right).
3. Consider strip of width 2δ around dividing line.
4. For each point in strip, check at most 7 others (bounded by δ×2δ box argument).
5. Combine: O(n)

Recurrence: T(n) = 2T(n/2) + O(n) (if y-sorted) → Θ(n log n)
Or T(n) = 2T(n/2) + O(n log n) (if re-sort by y each time) → Θ(n log²n)

8. Maximum Subarray (Kadane vs D&C)

D&C approach: Max subarray is entirely in left half, entirely in right half, or crosses midpoint.
Crossing subarray: max suffix of left + max prefix of right, computed in O(n).
T(n) = 2T(n/2) + O(n) → Θ(n log n)

Kadane’s algorithm (DP): O(n) time, O(1) space — strictly better.
D&C version illustrates the paradigm but is not optimal here.

9. GATE Examples

GATE 2015: T(n) = 7T(n/2) + 18n². What is T(n)?
p = log₂7 ≈ 2.81. f(n) = 18n² = O(n^2.81−ε). Case 1: T(n) = Θ(n^log₂7).

GATE 2017: Number of comparisons in worst case of binary search for n elements:
Answer: ⌊log₂n⌋ + 1 (including equality check at each step). For n=8: 4 comparisons.

GATE 2021: T(n) = 3T(n/2) + n. Solve.
p = log₂3 ≈ 1.585. f(n)=n=O(n^1.585−ε). Case 1: T(n)=Θ(n^log₂3).

10. Common Mistakes

Forgetting the combine step in recurrence: T(n)=2T(n/2) is wrong for merge sort; it must be T(n)=2T(n/2)+n.
Strassen saves 1 multiplication per level: 7 multiplications vs 8 — not 7 multiplications total; the saving is at each recursive level.
Binary search on unsorted array: Binary search requires sorted input. Applying it to unsorted arrays gives incorrect results.
Quick sort worst case on sorted input: Using the first element as pivot on an already-sorted array always creates 1:n−1 partitions, giving Θ(n²).
Closest pair checking only 1 point per strip point: Must check up to 7 points (not 1 or unlimited); the geometric argument limits the count.

11. FAQ

What are the three steps of divide and conquer?: Divide: split problem into a subproblems each of size n/b. Conquer: solve each subproblem recursively (base case solved directly). Combine: merge the solutions. The recurrence T(n)=aT(n/b)+f(n) captures all three, where f(n) is the divide+combine cost.
Why is Strassen’s algorithm faster than naive matrix multiplication?: Naive multiplication of block matrices requires 8 recursive multiplications, giving T(n)=8T(n/2)+O(n²)=Θ(n³). Strassen reformulates to need only 7 multiplications (with more additions), giving T(n)=7T(n/2)+O(n²)=Θ(n^2.81). Each reduction of 1 multiplication per level compounds exponentially across recursion levels.
What is the time complexity of binary search?: T(n)=T(n/2)+O(1). By Master theorem: a=1, b=2, p=log₂1=0. f(n)=O(1)=Θ(n⁰). Case 2 (k=0): T(n)=Θ(n⁰log n)=Θ(log n).
How does the closest pair of points algorithm achieve O(n log n)?: Divide by median x. Solve each half. Combine: find all points within δ of dividing line (the strip). For each strip point, only the 7 points in a δ×2δ box need checking (geometry proves at most 8 points fit). With pre-sorting by y, combine is O(n), giving T(n)=2T(n/2)+O(n)=Θ(n log n).

Divide and Conquer Algorithms – GATE CS | EngineeringHulk