# FFT: Multiplying multiple poynomials in O(KSlogS) time

I have a problem where I have to use the Fast Fourier Transform (FFT) algorithm $$K$$ polynomials $$P_1,...,P_K$$ where $$\mbox{deg}(P_1) + · · · + \mbox{deg}(P_K) = S$$.

I have to show that I can find the product of these $$K$$ polynomials in $$O(S\mbox{log}S\mbox{log}K)$$.

I know that the run time of FFT is $$O(n\mbox{log}n)$$. So far I only find the solution in $$O(KS\mbox{log}S)$$ time. The hints say to use trees and divide-and-conquer method but I'm still so blank.

Any hints and helps are greatly appreciated! Thank you.

• Hint: You can multiply two polynomials in $O(S \log S)$ time. The product is a polynomial of degree at most $S$. – Obinna Okechukwu Mar 27 at 0:59
• Btw, this looks like a homework problem. Please give proper citation. – Obinna Okechukwu Mar 27 at 1:11

Consider a binary tree of polynomials whose leafs are the polynomials $$P_1, P_2, \cdots, P_K$$.
The root node of this tree will eventually contain the polynomial $$P_1 P_2 P_3 \cdots P_K$$.
Each internal node can be computed in $$O(S \log S)$$, so total time to compute the tree is $$O(S\mbox{log}S\mbox{log}K)$$, since the height of the tree is $$\log K$$.