# Time complexity of inner product of two vectors of polynomials

Let’s say we have two vectors of polynomials $$p = [p_1(x), p_2(x),…,p_n(x)]$$ and $$q= [q_1(x), q_2(x),…,q_n(x)]$$ where elements $$p_i(x)$$ and $$q_i(x)$$ are polynomials of degree $$n$$ , each. Also, let’s say the polynomials $$p_i(x)$$ and $$q_i(x)$$ are given to me in the evaluation domain, i.e., $$p_i(x)$$ is given as $$[p_i(0), p_i(1),p_i(2),\ldots,p_i(n)]$$. I want to note that, we are given only $$n+1$$ points on each of the input polynomials.

I want to compute the inner-product of the vectors $$p$$ and $$q$$, i.e., compute the polynomial $$r(x) = \sum^n_{i=1} p_i(x)\cdot q_i(x)$$.

My question is, what is the time complexity of computing the polynomial $$r(x)?$$ A naive way is to first compute $$p_i(x).q_i(x)$$ for every $$i$$. This will cost me $$O(n\log n)$$ using number theoretic transform (NTT) for each $$i$$. Hence the total time will be $$O(n^2 \log n)$$. I wonder if the inner product can be computed in time $$O(n^2)$$?

I am fine with either representation of $$r(x)$$, i.e., either $$r(0), r(1),r(2),\ldots,r(2n)$$ or the coefficients of $$r(x)$$.

Probably not. Winograd proved in his paper: On the algebraic complexity of inner product that the computation of the inner product in a ring takes $$\Omega(n)$$ ring multiplications. Our ring in this case is $$R[x]$$, for some other ring $$R$$.
Currently, the best known algorithm to compute the product of 2 polynomials of degree $$n$$ in $$R[x]$$ uses $$\mathcal{O}(n \log(n))$$ ring operations in $$R$$.
Hence, $$\mathcal{O}(n^2 \log(n))$$ is the best we can do at the moment, it can only be improved if a faster polynomial multiplication algorithm is found.