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.

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

Consider a binary tree of polynomials whose leafs are the polynomials $P_1, P_2, \cdots, P_K$.

Each internal node of this tree is computed by taking the product of the polynomials on its left and right node.

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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.