What is a loop invariant?

Attilah picture Attilah · Jul 11, 2010 · Viewed 173.3k times · Source

I'm reading "Introduction to Algorithm" by CLRS. In chapter 2, the authors mention "loop invariants". What is a loop invariant?

Answer

Tomas Petricek picture Tomas Petricek · Jul 11, 2010

In simple words, a loop invariant is some predicate (condition) that holds for every iteration of the loop. For example, let's look at a simple for loop that looks like this:

int j = 9;
for(int i=0; i<10; i++)  
  j--;

In this example it is true (for every iteration) that i + j == 9. A weaker invariant that is also true is that i >= 0 && i <= 10.