1
$\begingroup$

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?

$\endgroup$

2 Answers 2

1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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[0]
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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.