# Computing coefficients of $p(x)^n$ in time $O(n \log n)$

For homework I've to give an algorithm that computes the coefficients of the polynomial $$p(x)^n$$ in time $$O(n\log n)$$, where $$p(x)$$ is a polynomial of degree 7.

As an hint I'm told to consider first the case where $$n$$ is a power of 2.

My guess is that I should use FFT and somehow manipulate it with modulo operations (maybe using the fact that for even powers the unity roots of power $$n$$ are the same as for $$n/2$$, only twice) but I'm pretty clueless about this one.

• Couldn't you use an algorithm based on fast exponentiation? May 12 at 8:41
• @Nathaniel Maybe, but I don't really see how May 12 at 13:02

Suppose $$n = 2^k$$ and for $$0\leq i \leq k$$, set $$p_i(x) = p(x)^{2^i}$$. We want to efficiently compute $$p_k(x)$$.
It is clear that for $$0\leq i < k$$, $$p_{i+1}(x) = p_i(x)^2$$. Using the Cooley-Tukey algorithm, knowing $$p_i(x)$$, we can compute $$p_{i+1}(x)$$ in time complexity $$O(d_i\log d_i)$$ where $$d_i = \deg p_i = \deg p \times 2^i = 7\times 2^i$$.
We can know compute $$p_k(x)$$ by successively computing $$p_1, p_2, …, p_{k-1}$$. The total time complexity will be:
$$O\left(\sum\limits_{i=0}^{k-1} i 2^i\right) = O(k2^k) = O(n\log n)$$
Now for the general case where $$n$$ is not a power of two, you can choose the intermediate polynomials you compute based on the binary decomposition of $$n$$, like in fast exponentiation.