Hint: Recurrences

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?

Hint: We make three recursive calls on problems of size k/2, and outside of the recursive call we take O(k) time. What is the recurrence?

Answer.