Date: January 7 2021
Summary: Statements used to show the correctness of an algorithm
Keywords: ##zettel #computer #science #archive
Not Available
Loop Invariant: a statement which explains why an algorithm is correct. [1]
It is comprised of three steps: Initialization: The statement is valid before the first iteration of the loop. Maintenance: If it is true before a loop iteration, it remains true throughout the loop. Termination: At the loop's end, the invariant yields a property to aid in showing the algorithm works expectedly.
Zelko, Jacob. Loop Invariants. https://jacobzelko.com/01072021071650-loop-invariants. January 7 2021.
[1] T. H. Cormen, Ed., Introduction to algorithms, 3rd ed. Cambridge, Mass: MIT Press, 2009.