- #1
drago
- 6
- 0
Hi,
I would appreciate if you could point me some resources that you have seen and think could be related to the following problem:
Given are the values of two polynomials Y(x) and Q(x) in n consecutive points (x0, x1,…, xn-1): (y0, y1,…,yn-1) and (q0, q1,…,qn-1) respectively.
We would like to evaluate the following sums:
S0 = (y0 – q0)^2 + (y1 – q1)^2 + …. + (yn-1 – qn-1)^2
S1 = (y0 – q1)^2 + (y1 – q2)^2 + …. + (yn-2 – qn-1)^2
S2 = (y0 – q2)^2 + (y1 – q3)^2 + …. + (yn-3 – qn-1)^2
….
Sn-1 = (y0 – qn-1)^2
Now, the question is, can I represent Sk as function of Sk-1? The point is, that I can evaluate Sk from the above representation, but this would have linear time complexity O(n), and there should be some way for this to be done in constant time, once we know S0 through Sk-1.
Thank you
drago
I would appreciate if you could point me some resources that you have seen and think could be related to the following problem:
Given are the values of two polynomials Y(x) and Q(x) in n consecutive points (x0, x1,…, xn-1): (y0, y1,…,yn-1) and (q0, q1,…,qn-1) respectively.
We would like to evaluate the following sums:
S0 = (y0 – q0)^2 + (y1 – q1)^2 + …. + (yn-1 – qn-1)^2
S1 = (y0 – q1)^2 + (y1 – q2)^2 + …. + (yn-2 – qn-1)^2
S2 = (y0 – q2)^2 + (y1 – q3)^2 + …. + (yn-3 – qn-1)^2
….
Sn-1 = (y0 – qn-1)^2
Now, the question is, can I represent Sk as function of Sk-1? The point is, that I can evaluate Sk from the above representation, but this would have linear time complexity O(n), and there should be some way for this to be done in constant time, once we know S0 through Sk-1.
Thank you
drago