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? 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 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.) Sep 25 '17 at 19:04
• Yeah that gives O(nlog(n)) using FFT--good, but I wonder if you can do better. Sep 25 '17 at 20:57