KEMBAR78
Loop Invariant | PDF | Control Flow | Invariant (Mathematics)
Scribd
Upload
40 views14 pages

Loop Invariant

The document discusses the concept of loop invariants in algorithm design, emphasizing their role in proving algorithm correctness and analyzing running time. It outlines the three essential conditions for a loop invariant: initialization, maintenance, and termination. Additionally, it provides examples of how to apply loop invariants in designing algorithms, particularly in determining maximum values in a dataset.

Uploaded by

shanicrazyf
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
40 views14 pages

Loop Invariant

The document discusses the concept of loop invariants in algorithm design, emphasizing their role in proving algorithm correctness and analyzing running time. It outlines the three essential conditions for a loop invariant: initialization, maintenance, and termination. Additionally, it provides examples of how to apply loop invariants in designing algorithms, particularly in determining maximum values in a dataset.

Uploaded by

shanicrazyf
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 14

Design and Analysis of

Algorithm
Muhammad Umer Mehmood
Loop Invariant
Describing Algorithms
• The Algorithm expressed in whatever way is clearest and most
concise, can be English or pseudocode
• A proof of the algorithms' correctness
• A derivation of the algorithms' running time.
Loop Invariant

“A loop invariant is a statement about program variables that is true


before and after each iteration of a loop.”
Loop Invariant
• Loop invariant proofs might seem scary at first, in particular, if you are
not used to writing mathematical proofs.
• when you plan to write a loop invariant proof, you already have an
algorithm and you have an intuitive notion of why the algorithm is
correct.
• Loop invariant proofs provide you with a very structured way of
translating your intuition into something solid.
Loop Invariant
Loop invariant must satisfy 3 conditions:
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
Loop Invariant
Loop Invariant

The loop invariant hold initially since sum = 0, i = 1 at this point


Loop Invariant

Assume the invariant holds before the ith iteration, it will be true
also after this iteration since the loop adds i to the sum, and
increments by i by one.
Loop Invariant

When the loop just about to terminate, the invariant states the
sum = 1 + 2 + 3 +………+n when the program leaves the loop.
Designing with Invariant
Designing with Invariant
• The invariant seems to be well chosen: it satisfies the termination
property since, the variable max = max(A[0], A[1],…….., A[n-1]) when
loops terminate.
• We can try to satisfy the initialization property by assigning a suitable
value to max. However, it’s not clear how to define the maximum
value of an empty slice.
Designing with Invariant
Designing with Invariant
• Now it’s easy to solve the problem. If we let max = A[0] and start the
loop with i = 1, the invariant holds when we first enter the loop.
• When doing we can assume that the variant holds at the beginning of
the loop.
• The maintenance property states: if the variant true before an
iteration of the loop, it should be true also after the iteration.

You might also like