Divide and Conquer Break problem into smaller sub-problems. example: multiplication Multiplying by powers of ten is easy, so we can break a multiplication into smaller groups. For instance, we can break n digit integer into:
\begin{equation} [x_1, x_2, \dots, x_{\frac{n}{2}}] \times 10^{\frac{n}{2}} + [x_{\frac{n}{2}+1}, x_{\frac{n}{2}+2}, \dots] \end{equation}
Then we can multiply two large values by writing:
\begin{align} x \times y &= \left(a \times 10^{\frac{n}{2}} + b \right) \left(c \times 10^{\frac{n}{2}} + d\right) \\ &= \left(a \times c \right) 10^{n} + \left(a \times d + c \times b\right) 10^{\frac{n}{2}} + \left( b \times d\right) \end{align}
Doing this is still 4^{\log_{2}\left(n\right)} = n^{2}, which is where we started. Karatsuba Integer Multiplication If we don’t have to compute 4 multiplication terms, it can be better. We can make this not 4 terms by observing that computing: ac bd \left(a+b\right) \left(c+d\right) = ac + bd + bc + ad We can get the middle term by \left(a+b\right) \left(c+d\right) - ac - bd. This is now 3^{\log_{2}\left(n\right)} \approx n^{1.6}, which is more efficient.