Author: Unknown
Subject: Loop Invariants
Date: Monday, 02 Mar 2020, 01:04:31

How do you pick a good loop invariant? and should it tell us anything about the algorithm?

You mentioned in class that loop invariants can be used to check if the output of an algorithm is correct. Does that mean the loop invariant must somehow relate the input with the output?

Let's say we have the following loop:
  
  sum = 0;
  for (int i=0; i<5; i++) {
    sum +=i;
  }

Can the loop invariant be something like i<=sum? Would it be a good loop invariant? If so, would it tell us anything significant?