I want to know about loop invariant. I came to know that in algorithms(mainly sorting algorithms) have a loop invariant and loop invariant indicates the correctness of an algorithm.
How does this work? Can someone help me in understanding this?
Asked
Active
Viewed 294 times
1 Answers
2
A loop invariant does not, in itself, indicate correctness of an algorithm. It is a predicate that is true for each iteration of the loop. (You usually need to prove that the predicate is, indeed, invariant for the loop.) The invariant can then be used to prove various properties of the loop (including, perhaps, correctness). The Wikipedia article Loop invariant has some examples that show how this can work. See this thread for more examples and explanations.
