Рассмотрим не только многочлены, но и функции.

Пусть мы хотим посчитать произведение двух многочленов $P(x) = \sum\limits_{k=0}^n p_k \cdot x^k$ и $Q(x) = \sum\limits_{k=0}^n q_k \cdot x^k$.

Попробуем применить метод «разделяй и властвуй», чтобы добиться временной сложности меньшей, чем $O(n^2)$. В лоб, к сожалению, не получится. Применим хитрость.

Сгруппируем множители в многочленах $P$ и $Q$ степени $n = 2k$, превратив каждый многочлен в пару многочленов степени $k$.

Произведение $P(x) \cdot Q(x)$ можно произвести, используя только $3$ умножения маленьких многочленов, вместо привычных $4$:

При таком алгоритме на итерацию требуется $3$ умножения и $6$ сложений. Пусть алгоритм, вычисляющий произведение двух многочленов степени $n$, требует $M(n)$ умножений и $A(n)$ сложений.

Оценим количество умножений. Как мы уже говорили, можно дополнить многочлены нулями до длины $2^{\lfloor \log_2 n \rfloor + 1}$. Тогда вычисления будут проще, но количество умножений возрастет.

Важное неравенство, позволяющее оценить количество требуемых умножений

То есть, алгоритм Карацубы (в обоих вариантах, с дополнениями нулями и без) требует $\Theta \bigl( n^{\log_2 3} \bigr)$ умножений.

Накладные расходы на рекурсию иногда становятся слишком большими. Можно выполнять алгоритм Карацубы только пока степени многочленов больше какого-то числа $N_{\max\limits}$. Для многочленов, чьи степени меньше $N_{\max\limits}$, выполняем обычное умножение.

На практике $N_{\max\limits}$ выбирают $32$ или $64$.