# Computational complexity of polynomial interpolation with k non-zero terms

I am attempting to find a complexity for computing the order polynomial of partially ordered sets on a special family, and have come across the following problem. Assume we have the following values from a polynomial: $P(0)...P(n-k)=0$ and $P(n-k+1)...P(n)=y_{n-k+1}...y_n$: what is the complexity of polynomial interpolation in this environment?

Looking at the Lagrange polynomials, the first n+1-k become 0, and the k last follow a simple form:

$L_i = \frac{\Gamma(x+1)\Gamma(i-n)y_i}{\Gamma(x-n)\Gamma(i+1)(x-i)}$

This suggests to me the coefficients for each x should have some nice form. However I'm a bit lost at this point as to the complexity of computing the $L_i$ (which we need k of), perhaps there is a better method?

• I'm not sure precisely what it is you're asking. Does replacing $\frac{\Gamma(x+1)}{(x-i)\Gamma(x-n)}$ by $\prod_{j=0, j\ne i}^n (x-j)$ and similar for $\Gamma(i-n)/\Gamma(i+1)$ solve your problem? – Andrew Morgan Sep 25 '17 at 14:31
• Sorry my overall question is simply what is the computational complexity of polynomial interpolation with the specifications given above. The rest was my rather unsuccessful attempt to simplify the problem – Max Hopkins Sep 25 '17 at 18:50
• Ah okay. I'm not sure whether it helps here, but if P' is the degree-at-most-(k-1) polynomial that agrees with P on the last k points, then $P = (x)(x-1)\cdots(x-n+k) \cdot P'$. So ignoring the cost of multiplying/dividing by the left factor, finding P is equivalent to arbitrary degree-(k-1) polynomial interpolation, since P' is essentially arbitrary. (All of these operations are computable in polynomial time, but I don't know the exact complexities off-hand.) – Andrew Morgan Sep 25 '17 at 19:04
• Yeah that gives O(nlog(n)) using FFT--good, but I wonder if you can do better. – Max Hopkins Sep 25 '17 at 20:57