Skip to content

Instantly share code, notes, and snippets.

@sachinlala

sachinlala/LoopInvariant.md

Last active May 10, 2018 05:53
Show Gist options
  • Save sachinlala/2153509dc3d51eb4416da9d81b22ac99 to your computer and use it in GitHub Desktop.
Save sachinlala/2153509dc3d51eb4416da9d81b22ac99 to your computer and use it in GitHub Desktop.
Download ZIP
What is a Loop Invariant ?
Raw
LoopInvariant.md

A loop invariant is a set of conditions that are:

  1. true when the loop is initialized
  2. maintained in each pass through the loop
  3. true at termination

Loop invariant arguments are analogous to mathematical induction: they use a base case along with an inductive step to show that the desired proposition is true in all cases.

For example, one feasible loop invariant for the kth largest/smallest algorithm would be the following:

At each iteration, the “active subarray” (call it activeA) consists of all elements of A which are between min(activeA) and max(activeA), and the current index (call it i) has the property that the ith-smallest element of activeA is the ith-smallest element of A.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment