Loop Invariant in Analysis of Algorithm

  • Thread starter sdj
  • Start date
  • #1
sdj
4
0
I can't generally map Loop Invariant method for proving the correctness of an Algorithm. Take the case of an Insertion Sort

http://csnx.groups.allonline.in/pool/Introduction%20to%20Algorithms-Cormen%20Solution.pdf

in the above link, at the page 2-3, they have proved the correctness of insertion sort using loop invariant. As of I understood, a loop invariant is a condition that will exist in an Algorithm(not necessarily), which always holds true, irrespective of the state of the Algorithm. And how is this used in proving the correctness? Besides in the same book it has been mentioned:

"Note the similarity to mathematical induction where to prove the property holds, you prove a base case and inductive step. Here, showing that the invariant holds before the first iteration corresponds to the base case and showing that the invariant holds from iteration to iteration corresponds to the inductive step."

Here, I can understand the lines above, but still not convinced with the explanation. Can anyone help me out...??
 

Answers and Replies

  • #2
35,139
6,892
I can't generally map Loop Invariant method for proving the correctness of an Algorithm. Take the case of an Insertion Sort

http://csnx.groups.allonline.in/pool/Introduction%20to%20Algorithms-Cormen%20Solution.pdf

in the above link, at the page 2-3, they have proved the correctness of insertion sort using loop invariant. As of I understood, a loop invariant is a condition that will exist in an Algorithm(not necessarily), which always holds true, irrespective of the state of the Algorithm. And how is this used in proving the correctness? Besides in the same book it has been mentioned:

"Note the similarity to mathematical induction where to prove the property holds, you prove a base case and inductive step. Here, showing that the invariant holds before the first iteration corresponds to the base case and showing that the invariant holds from iteration to iteration corresponds to the inductive step."

Here, I can understand the lines above, but still not convinced with the explanation. Can anyone help me out...??

See the wiki article - http://en.wikipedia.org/wiki/Loop_invariant
 

Related Threads on Loop Invariant in Analysis of Algorithm

Replies
16
Views
4K
Replies
9
Views
908
Replies
3
Views
2K
  • Last Post
Replies
3
Views
2K
  • Last Post
Replies
0
Views
4K
  • Last Post
Replies
3
Views
11K
  • Last Post
Replies
1
Views
671
  • Last Post
Replies
6
Views
2K
  • Last Post
2
Replies
41
Views
43K
  • Last Post
Replies
4
Views
2K
Top