Karatsuba and Strassen multiplication; closest pair (brief)

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

• Multiplications for x¹⁶ by squaring? from Lesson 4.1.1
• T(n) = 7T(n/2) + n²? from Lesson 1.2.3
• T(n) = 3T(n/2) + n? from Lesson 1.2.3

1 · The Hook

🎣

Schoolbook multiplication of two n-digit numbers takes n² digit products. In 1960 Karatsuba found a way with only three half-size products instead of four, and the exponent dropped from 2 to 1.585. Strassen did the same for matrices: seven half-size products instead of eight. GATE asks for these recurrences and exponents.

2 · Predict First

🤔

Splitting two n-digit numbers into halves (x = a·10^(n/2) + b, y = c·10^(n/2) + d) gives xy = ac·10ⁿ + (ad + bc)·10^(n/2) + bd: four half-size products. What is the running time if you compute all four recursively, with linear-time additions?

Make a guess in your head. The answer opens Section 3.

3 · Core Concept

💡

Predict First — the answer

T(n) = 4T(n/2) + Θ(n) → n^(log 4) = Θ(n²): no better than the schoolbook method.

Karatsuba multiplication

Compute only three products: ac, bd and (a + b)(c + d). Then ad + bc = (a + b)(c + d) − ac − bd.

• T(n) = 3T(n/2) + Θ(n) → Θ(n^(log 3)) ≈ Θ(n^1.585).
• For n = 2ᵏ digits the recursion performs 3ᵏ single-digit multiplications (n = 8: 27 instead of 64).

Matrix multiplication

• Schoolbook: n³ scalar multiplications.
• Block divide and conquer (each matrix as four n/2 × n/2 blocks): 8 block products → T(n) = 8T(n/2) + Θ(n²) → Θ(n³): no gain.
• Strassen: 7 block products and 18 block additions/subtractions → T(n) = 7T(n/2) + Θ(n²) → Θ(n^(log 7)) ≈ Θ(n^2.81). For n = 2ᵏ: 7ᵏ scalar multiplications (n = 8: 343 instead of 512).

Closest pair of points (brief)

Sort points by x, split at the median line, solve each half, then check only points within distance δ of the line (at most a constant number per point, sorted by y): T(n) = 2T(n/2) + Θ(n) → Θ(n log n) (with a presort).

The general lesson

In aT(n/b) + f(n) with f small, the leaves dominate: reducing a (the number of subproblems) lowers the exponent log_b a. That is all Karatsuba and Strassen do.

4 · Visual

5 · Worked Examples

Example 1 Easy

How many single-digit multiplications does Karatsuba use for two 16-digit numbers (splitting down to 1 digit)?

Solution

16 = 2⁴ → 3⁴ = 81.

Example 2 Medium

How many scalar multiplications does Strassen use for two 16 × 16 matrices (recursing down to 1 × 1)?

Solution

7⁴ = 2,401 (instead of 16³ = 4,096).

Example 3 GATE

Suppose a method multiplies two n × n matrices using 6 multiplications of n/2 × n/2 matrices plus Θ(n²) extra work. Its time?

Solution

T(n) = 6T(n/2) + n² → n^(log 6) ≈ Θ(n^2.585).

6 · GATE Traps

⚠️

• Block matrix multiplication with 8 products is still Θ(n³).
• Karatsuba's exponent is log₂ 3, Strassen's log₂ 7.
• Fewer subproblems matter; the extra additions only affect f(n).
• Closest pair needs the strip check to be linear to stay n log n.

7 · Memory Hook

🧠

"Three for numbers, seven for matrices."

8 · Connect the Dots

Chapter 4.1 is complete. Chapter 4.2 switches to a different idea: instead of solving all subproblems, make one locally best choice and never look back. When that works, the algorithm is a greedy algorithm.

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1MCQ1 markKaratsuba

Karatsuba's algorithm multiplies two n-digit numbers in:

• (A) Θ(n^(log 3))
• (B) Θ(n log n)
• (C) Θ(n^(log 7))
• (D) Θ(n²)

Q2NAT1 markStrassen count

Scalar multiplications by Strassen's method for 4 × 4 matrices (recursing to 1 × 1)?

Numerical answer: ________

Q3NAT2 marksExponent

A recursive method splits n × n matrices into 3 × 3 blocks of size n/3 and uses 23 block multiplications plus Θ(n²) work. T(n) = Θ(nᵏ); k to 2 decimals?

Numerical answer: ________

Q4MCQ1 markBlock D&C

Plain block matrix multiplication with 8 recursive products runs in:

• (A) Θ(n²)
• (B) Θ(n^2.81)
• (C) Θ(n³ log n)
• (D) Θ(n³)

Q5NAT1 markKaratsuba count

Single-digit multiplications by Karatsuba for two 32-digit numbers?

Numerical answer: ________

10 · Rule Card

• 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.

11 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

Karatsuba multiplicationthree-product trickblock matrix multiplicationStrassen's algorithmclosest pair of pointsreducing the number of subproblems

12 · Answer Vault