Loop invariants

  1. What is loop invariant? (obviously!)
  2. Example of loop invariant. (to keep this concept in our brains!)
  3. Usage. (after all, we have to use it!)

// the Loop Invariant must be true here
for ( TEST CONDITION ) {
// top of the loop


// bottom of the loop
// the Loop Invariant must be true here
}
  1. Initialization: The loop invariant must be true before the first execution of the loop.
  2. Maintenance: If the invariant is true before an iteration of the loop, it should be true also after the iteration.
  3. Termination: When the loop is terminated the invariant should tell us something useful, something that helps us understand the algorithm.
//insertion sortfor (i = 1 to n-1)
{
key = arr[i];
j = i-1;
//insert A[i] into the sorted sequence A[0 .. i-1] while (j >= 0 and arr[j] > key)
{
arr[j+1] = arr[j];
j = j-1;
}
arr[j+1] = key;
}
I designed this using Canva. Hope you liked it. :-)
  • Loop invariants can be used to prove the correctness of an algorithm, debug an existing algorithm without even tracing the code.
  • Trial and method can be used to write easy algorithms but it is better to use formal methods like loop invariants when the complexity of the problem increases. In this way, loop invariants are used to reason about the correctness of computer programs.
  • A loop Invariant can help in the design of iterative algorithms.

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store