Question: Notice that regular grade-school multiplication of two k-digit numbers takes O(k^2) time. Consider the following alternative technique.
MULTIPLY(a, b)
k <- max(number of digits in a, number of digits in b)
//base case
if k = 1 then return a * b fi
a_U <- upper k/2 digits of a
a_L <- lower k/2 digits of a
b_U <- upper k/2 digits of b
b_L <- lower k/2 digits of b
x_1 <- MULTIPLY(a_L, b_L)
x_2 <- MULTIPLY(a_U, b_U)
x_3 <- MULTIPLY(a_U + a_L, b_U + b_L) - x_1 - x_2
return x_2 * 10^k + x_3 * 10^(k/2) + x_1
Addition, subtraction, and multiplying by the O(k)th power of 10 take O(k) time. Knowing this, how much time will MULTIPLY take on two k-digit numbers?
Answer: The recurrence is
T(k) = 3 T(k / 2) + c kThe solution to this, as outlined in class, is
T(k) = Theta(n^(log_2 3)) ~= Theta(n^1.585)