# Multiplying n polynomials of degree 1

The problem is to compute the polynomial $(a_1 x + b_1) \times \cdots \times (a_n x + b_n)$. Assume that all coefficients fit in a machine word, i.e. can be manipulated in unit time.

You can do $O(n \log^2 n)$ time by applying FFT in a tree fashion. Can you do $O(n \log n)$?

• Nice question, seems like I've seen something similar in someone's blog, but I can't remember where it was. – Grigory Yaroslavtsev Aug 27 '10 at 19:51
• Minor observation: we know (working over Q, say) the n roots $\alpha_i = -b_i/a_i$, so the problem is equivalent to: Given $\alpha_1, \dots , \alpha_n$, compute the polynomial $(x-\alpha_1)\dots(x-\alpha_n)$. (I guess.) – ShreevatsaR Aug 28 '10 at 2:43
• Can you give a reference to the $O(n\log^2 n)$ result? – Mohammad Al-Turkistany Sep 10 '10 at 2:14
• As @Suresh mentioned, it is a simple divide-and-conquer approach. It can be generalized so that n polys may have different degrees $d_i$, in which case you can divide in a Huffman tree fashion. See Strassen: The computational complexity of continued fractions. – Zeyu Sep 10 '10 at 4:47
• Can we compute the convolution of $n$ vectors of constant dimension 2 in time $O(n \log n)$? – Kaveh Sep 10 '10 at 14:14

• On the other hand, an $\Omega(n\log^2 n)$ lower bound for such a natural problem seems equally implausible! – Jeffε Sep 27 '10 at 6:46