CODEWITHSUNDEEP
algorithmloop-invariant
Tyler Dahle
Tyler Dahle

Reputation: 77

Loop invariant and using to solve algorithm?

So if I have the following code:

public int sumSquares(int n){
   int sum = 0;
   for(int i = 1; i <=n; i++){
      sum += i*i;
   }
   return sum;
}

I must now find a loop invariant. I was told that for a loop like this, an invariant of Y = i^2 is considered a loop invariant, however I don't know if I get how to prove it is a loop invariant. Since Y is just something, then it is always true before, during, and after the loop because it is whatever i*i is... Is that a valid proof of it being an invariant?

Also, when it comes to proving the algorithm with the invariant, is it correct to say that sum = the sum from 1 to n of i*i (or Y, the loop invariant) = n(n+1)(2n+1)/6

Then use induction to show that that is correct? Is that properly using the loop invariant to prove the algorithm?

Would love some help :)

Upvotes: 2

Views: 197

Answers (1)

amit
amit

Reputation: 178421

The invariant should be, at the entrance to the loop, for any i,

sum = 0 + 1*1 + 2*2 + ... + (i-1)*(i-1)

The above claim can be proven by induction. Let sum be the variable at the beginning of the loop, and sum' the variable at its end, then:

sum' = sum + i*i = 0 + 1*1 + ... + i*i

This allows you to use the fact that in addiiton, when the loop terminates i=n+1, so when the program terminates, you get:

sum = 0 + 1*1 + ... + n*n

Upvotes: 1

Related Questions