The O(n^2\log^2 n) time algorithm can be found from the appendix of this paper of mine.
Now, let me present an O(n^2) time algorithm.
First, an EXPRESSION can be thought as a tree where all variables and constants are leaves and inner nodes are operations (* and +)
E.g. (x^2+x+1)(2x+1) corresponds to
(Algorithm 1)
1. Choose n+1 different numbers a_1, ...., a_{n+1} .
2. Evaluate the polynomial at these points, i.e., compute F(a_i). (each evaluation takes linear time (bottom-up over the tree). So O(n^2) time in total)
3. Use any O(n^2) polynomial interpolation algorithm to find the coefficient (actually reduces to finding a solution for a linear system).
Cute? Still have to rely on some other nontrivial algorithm to invert the Vandermonde system in O(n^2) time (ref [3][4] in the wiki page).
Let us look at a cuter one.
(Algorithm 2)
Suppose the polynomial if F(x)=\sum_j c_j x^j.
Let e_i be the n-dimensional zero vector except that the ith entry is 1, i.e.,e_i=(0,0,..,1,...,0,0).
Let d_i be the n-dimensional vector which is the DFT(discrete Fourier transformation) of e_i.
Denote u be the nth root of unit and u={1,u,u^2,....,u^{n-1}}.
Therefore, e_i[j]=\sum_k d_i[k] u^{jk}. Equivalently, e_i=\sum_k d_i[k] u^k
where u^k={1,u^k,u^{2k},u^{3k},.....}
Computing all d_i takes O(n^2) time.
Let c be the coefficient vector (of F).
c_i = <c, e_i> (inner product)
<c,e_i>=\sum_k d_i[k]<c, u^k>....................(1)
But what is <c,u^k>
Now, we have our algorithm:
1.compute d_i for all i ....................use DFT formula directly (don't need FFT) ,O(n^2)
2.compute F(u^k) for all k.....................n poly evaluations over complex, O(n^2)
3.use (1) to compute the coefficient.................O(n^2)
So, nothing fancy here(except the idea:). Cuter, right?
OPEN question: can we do better? or the lower bound is O(n^2)
