Loop Invariant -CLR

Question

What is loop invariant in general term ?

 

 

PS: Insertion Sort has loop invariant . We have three things in loop invariant :

a. Initialization

b.Maintenance

c.Termination

Comments

A loop invariant is basically a condition which remains true in all the three scenarios you mentioned.It will be true during initialization,while loop in iterating and end of loop.

---

Refer this https://stackoverflow.com/questions/3221577/what-is-a-loop-invariant

Answer 1

Loop invariant is a condition which is true for every iteration of loop.

loop invariant must be true

1. before the loop starts
2. before each iteration of the loop
3. after the loop terminates

Comments

Could u give one such example in general which will be easy to understand ?

---

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 loop invariant is a condition that is necessarily true immediately before and immediately after each iteration of a loop. (Note that this says nothing about its truth or falsity part way through an iteration. )

Source: http://www.cs.uofs.edu/~mccloske/courses/cmps144/invariants_lec.html