Invariant?

I was doing some practice problems on Linked Lists and I saw this question: "Which of the following does not satisfy the loop invariant for the while loop?"

My question is, what does invariant mean? I know it means constant in English, but what does it mean in math/computer science? I googled it and all this crap about predicate in mathematics came up. Wikipedia isn't really noob-friendly so I thought I post it here. Any help is appreciated and thanks in advance!

P.S. Let me know if posting the whole question will be beneficial.

edit: Answer wrong -- deleted.

Yes, seeing the whole question would help.

But I can elaborate on the definition of loop invariant for you; basically, it's a condition that's true when entering into a loop and remains constant through an entire loop.

Code:

---

int i = 1;
while (x < 5) {
    x++;
}

---

Here's a list of loop invariants:

• true
• x < 5
• x > 0

Here are some examples of loop variants (things that are NOT loop invariants; that is, they change during execution):

• x == 3
• x == 4
• x < 2

Remember to note: the conditions for a while loop (in the code above, "x < 5") are ALWAYS loop invariants, as the loop terminates once their value has changed.

I hope this helps a bit, Wikipedia actually has an entry on loop invariants you can find here. (I know you mentioned that Wikipedia isn't noob-friendly, but ignore the formulae and such and you'll get down to the actual concept beneath them.)

Good luck!

Quote:

---

Originally Posted by Zack

But I can elaborate on the definition of loop invariant for you; basically, it's a condition that's true when entering into a loop and remains constant through an entire loop.

---

Yep. Listen to Zack, not my answer. In fact, I'm going to delete it.

So a loop invariant is basically like a boundary on a variable before and after execution? Like what is the worse and best case scenario of a variable after it goes through some loop. Also, why is true in the list of invariants?

lol Fubarable I didn't even get a chance to read it. It's the thought that counts so thanks! :)

Quote:

---

Originally Posted by Lil_Aziz1

So a loop invariant is basically like a boundary on a variable before and after execution? Like what is the worse and best case scenario of a variable after it goes through some loop. Also, why is true in the list of invariants?

---

true is in the list because its value never changes. I could also put 7, false, 13.3f, and so on, because they have constant values. 7 will be 7 before the loop and after the loop, no matter what you do. ;)

Think of it like this:
http://img20.imageshack.us/img20/854...invariants.png
(Top row is the iteration; left column is the statement evaluated for each iteration.)
Here I've put in red the loop variants, and the blue lines are loop invariants. Notice that in the red lines, you will see more than one value (i.e. it's not all true or all false). Hence, the value of that boolean statement is variant.

I hope that helps explain it a bit; if not I'll give it another whack. ;)