Integer multiplication
<MATH> \begin{array}{rrrrr} & & 1 & 2 & 3 \\ & & 4 & 5 & 6 \\ \hline & & 7 & 3 & 8 \\ & 6 & 1 & 5 & - \\ 4 & 9 & 2 & - & - \\ \hline 5 & 6 & 0 & 8 & 8 \end{array} </MATH> To form a partial products, we need
We need then at most <math>2n</math> operations.
If we have <math>n</math> partial products (The number of digits in the second number), the total is at most <math>2n^2</math> operations to form all of them.
The final addition requires at most a comparable number of operations. <math>2n^2</math> .
The number of operations for this Algorithm performs roughly <math>4n^2</math> It's quadratic function in the input of length n.
Assumption: n is an even integer. If n is an odd integer, you can apply this exact same recursive approach to integer multiplication. If n was 9, the input numbers would be decomposed into a first five digits and a later four digits and you would proceed in exactly the same way.
<MATH> \begin{array}{rrl} x & = & 10^{n/2} a + b \\ y & = & 10^{n/2} c + d \end{array} </MATH> where:
Then
<MATH> \begin{array}{rrl} x.y & = &(10^{n/2} a + b)(10^{n/2} c + d) \\ & = & 10^{n} ac + 10^{n/2}(ad+bc) + bd \end{array} </MATH> Idea :
Recursivity base case: If the input (n) is sufficiently small (one digit), then compute the answer rather than recursing further.