Loop invariant?

Question

What is actually a loop invariant???

Answer 1

An loop invariant per se is something, which will stay the same no matter in which Iteration of the loop you are.
For example:
calculateSomething (int n)
1. int b = 1;
2. for int i = 1 to n do:
3. b = b * 5
4. return b

This is a rather simple example, but i hope it will be understandable enough.
This Code will basically calculate pow(5,n).
Now we are going to determine the loop invariant which is valid before any loop Iteration.
If you look closely, you will see that the output value can be written as b = 5 ^ -1 (-1 because of our condition that it should be valid before any Iteration) and this is also the invariant, because no matter which Iteration you are, if you take the number of Iteration and insert it, you will always get the right value before this Iteration starts.
I hope this explanation could help you a little.

Answer 2

*Addition l
Same principle goes for algorithms which sort arrays, for example Selection Sort. The loop invariant for this would be, that the first i elements are sorted before an Iteration. Best would be if you take a look into the book "Introduction to Algorithms" from Charles E. Leiserson, Clifford Stein, Ronald L. Rivest and Thomas H. Cormen (I think there is a PDF Version on the web), there's a Chapter for loop invariants and in my opinion it is very weil explained.