Hi,(adsbygoogle = window.adsbygoogle || []).push({});

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

**Physics Forums | Science Articles, Homework Help, Discussion**

Dismiss Notice

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Computing distances

**Physics Forums | Science Articles, Homework Help, Discussion**