I am reading Algorithms Unlocked By Tom Cormen and find this concept a little confusing.
Why is it that we require loop invariants and how does it help in analyzing algorithms?
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.Sign up to join this community
Loop invariants are crucial for showing an algorithm is correct (cf. proof by induction).
For example, suppose you need to sort an array of distinct integers. One simple way to do it is by using selection sort. Why is selection sort correct, i.e., why does it actually solve the problem? If we understand intuitively why the algorithm works, we can also formalize the loop invariant along the lines you mention: at every step, it holds that the subrange processed so far is sorted. So what happens at the end? The subrange equals the whole input range and not surprisingly, that subrange is now sorted as required of any solution for the problem.
We don't "require" loop invariants. They are a technique used when proving algorithm correctness.
Lets take a look at a simple example of how loop invariants are useful:
Consider the problem where we get an array $A$ and have to find the maximal value of it, i.e. compute $max(A)$.
We created the following algorithm for the problem, and we want to show that it indeed returns the maximal element in $A$.
cur_max = A for element in A: if element > cur_max: cur_max = element return cur_max
Now, this code is simple. Our loop invariant in this case would be "At the $k$'th iteration,
cur_max is the maximum value of all first $k$ elements in $A$".
Proving this loop invariant can be easily done in induction. But more importantly, what does this say to us when the loop is finished? It says that
cur_max is the maximum value of all elements in $A$, hence we get the correctness of the algorithm.