ACompressed recap
🧾
Divide and conquer: T(n) = aT(n/b) + f(n). Fast exponentiation: squarings plus one multiply per odd step, Θ(log n). Counting inversions inside merge sort: add the number of remaining left elements, Θ(n log n). Maximum subarray: left, right, crossing, Θ(n log n). Karatsuba 3T(n/2) + n → n^1.585 (3ᵏ products); Strassen 7T(n/2) + n² → n^2.81 (7ᵏ products); block multiplication with 8 products stays n³; closest pair Θ(n log n).
BMerged rule card
4.1.1 Divide and conquer: fast exponentiation, counting inversions, maximum subarray
- D&C: divide into a pieces of size n/b, conquer, combine in f(n): T = aT(n/b) + f(n).
- Fast power: Θ(log n) multiplications (squarings + one per odd step).
- Inversions via merge: add remaining-left count; Θ(n log n).
- Max subarray D&C: left, right, crossing; Θ(n log n).
4.1.2 Karatsuba and Strassen multiplication; closest pair (brief)
- Karatsuba: 3T(n/2) + n → n^(log 3) ≈ n^1.585; 3ᵏ digit products for n = 2ᵏ.
- Strassen: 7T(n/2) + n² → n^(log 7) ≈ n^2.81; 7ᵏ scalar products.
- Block matrix with 8 products: n³. Closest pair: n log n.
- Fewer subproblems → smaller exponent.
CInterleaved GATE-style questions
Q1NAT1 markPower
Multiplications to compute x¹³ by the recursive method?
Numerical answer: ________
Q2NAT2 marksPower
Multiplications to compute x¹⁰⁰ by the recursive method?
Numerical answer: ________
Q3NAT2 marksMax subarray
Maximum subarray sum of [−2, 1, −3, 4, −1, 2, 1, −5, 4]?
Numerical answer: ________
Q4MCQ1 markCrossing
In D&C maximum subarray, the crossing case is computed by:
- (A) the maximum element
- (B) the sum of the whole array
- (C) the best suffix of the left half plus the best prefix of the right half
- (D) recursion on both halves again
Q5NAT1 markStrassen
Scalar multiplications by Strassen for 32 × 32 matrices (down to 1 × 1)?
Numerical answer: ________
Q6MCQ1 markExponent
T(n) = 3T(n/2) + n is the recurrence of:
- (A) merge sort
- (B) Karatsuba multiplication
- (C) binary search
- (D) Strassen's algorithm
Q7NAT2 marksVariant
A method multiplies n-digit numbers by splitting into 3 parts and using 5 products of size n/3, plus Θ(n) work. T(n) = Θ(nᵏ); k to 2 decimals?
Numerical answer: ________
Q8MSQ2 marksD&C facts
Which are true?
- (A) Strassen's algorithm uses 7 recursive multiplications.
- (B) Reducing the number of subproblems can lower the exponent of a D&C algorithm.
- (C) Closest pair of points can be solved in Θ(n log n).
- (D) Karatsuba uses 4 recursive multiplications.
DAnswer Vault
Answer Vault
Try the questions first. Open when you are ready to check.
Q1 Answer: 51 mark
13 → 6 → 3 → 1: 3 squarings + 2 odd steps.
Re-read: Lesson 4.1.1 — Divide and conquer: fast exponentiation, counting inversions, maximum subarray
Q2 Answer: 82 marks
100 → 50 → 25 → 12 → 6 → 3 → 1: 6 squarings + 2 odd steps (25 and 3).
Re-read: Lesson 4.1.1 — Divide and conquer: fast exponentiation, counting inversions, maximum subarray
Q3 Answer: 62 marks
[4, −1, 2, 1].
Re-read: Lesson 4.1.1 — Divide and conquer: fast exponentiation, counting inversions, maximum subarray
Q4 Answer: (C)1 mark
Linear scan outward from the middle.
- (A) is wrong: Not necessarily the best stretch.
- (B) is wrong: Not necessarily maximal.
- (D) is wrong: Already done.
Re-read: Lesson 4.1.1 — Divide and conquer: fast exponentiation, counting inversions, maximum subarray
Q5 Answer: 168071 mark
7⁵.
Re-read: Lesson 4.1.2 — Karatsuba and Strassen multiplication; closest pair (brief)
Q6 Answer: (B)1 mark
Three half-size products.
- (A) is wrong: 2T(n/2) + n.
- (C) is wrong: T(n/2) + 1.
- (D) is wrong: 7T(n/2) + n².
Re-read: Lesson 4.1.2 — Karatsuba and Strassen multiplication; closest pair (brief)
Q7 Answer: 1.46 to 1.472 marks
log₃ 5 ≈ 1.465 (Toom-3).
Re-read: Lesson 4.1.2 — Karatsuba and Strassen multiplication; closest pair (brief)
Q8 Answer: (A) (B) (C)2 marks
Karatsuba uses 3.
- (D) is wrong: That is the naive split.
Re-read: Lesson 4.1.2 — Karatsuba and Strassen multiplication; closest pair (brief)