Simple algorithm performance

Question

Hi,

Can you please distinguish which formula would be computationally more effective:

1. Sn = 1/n * ∑(Xi - C)² | sum "i" till "n"

or

1. Sn = 1/n * ∑Xi² - C² | sum "i" till "n"

C is const.

First one has n squares and second one (n+1) squares

Thanks in advance

Answer 1

Is the second one 1/n*∑(Xi² - C²) or 1/n * ∑Xi² - C². If it is the first case, 1/n * ∑(Xi - C)² is more effective because it only performs one subtraction and one square for each i,but 1/n*∑(Xi² - C²) perform 2 square and 1 subtraction. If it is the second case, 1/n * ∑Xi² - C² performs only 1 square for each i, and C² is outside of the summation so it perform only once. C By the way, the two formulas are not the same. 1/n * ∑(Xi - C)² = 1/n * (∑Xi² - 2C*∑Xi + C²)

Answer 2

I'm not a math expert, but I'll take a stab at this, just for fun...

Everything in the equation is equivalent except for the (Xi-C)^2 part.

I think if you write that part out longhand, you'll get:

(Xi-C)(Xi-C)

Then using the FOIL method to expand again:

Xi^2 - 2XiC + C^2

Is 2XiC + C^2 greater than or less than -C^2? It appears to depend on what the value of C is. You both may have been right... :)