All Questions
3
questions
3
votes
1
answer
889
views
What is the most efficient algorithm to evaluate a polynomial of n degree at K points?
A brute force approach would be to evaluate each point for each of the terms of a polynomial, which will be $O(Kn^2)$.
If we use logarithmic exponentiation to find each $x^i$ then it becomes $O(Kn \...
- 491
0
votes
1
answer
145
views
$\left( 1 - \frac{1}{n} \right)\left( 1 - \frac{2}{n} \right) \cdot ... \cdot \left( 1 - \frac{k-1}{n} \right) = \frac{n!}{n^k r! (n-k-r)!}$
I'm trying to understand a proof in "Interpolation and Approximation by Polynomials" by Phillips.
Let me quote (page 253):
"For $k\geq 1$ we begin with $$B_{n+k}^{(k)}(f;x)=\frac{(n+k)!}{n!} \sum\...
- 143
11
votes
3
answers
827
views
A Curious Binomial Sum Identity without Calculus of Finite Differences
Let $f$ be a polynomial of degree $m$ in $t$. The following curious identity holds for $n \geq m$,
\begin{align}
\binom{t}{n+1} \sum_{j = 0}^{n} (-1)^{j} \binom{n}{j} \frac{f(j)}{t - j} = (-1)^{n} \...
- 17.1k