Question

What is the relationship between loop invariant,loop condition and the input-output recursively

Answer 1

Explanation:

Loop Invariant Condition:

Loop invariant condition is a condition about the relationship between the variables of our program which is definitely true immediately before and immediately after each iteration of the loop.

For example: Consider an array A{7, 5, 3, 10, 2, 6} with 6 elements and we have to find maximum element max in the array.

max = -INF (minus infinite)

for (i = 0 to n-1)

if (A[i] > max)

max = A[i]

In the above example after 3rd iteration of the loop max value is 7, which holds true for first 3 elements of array A. Here, the loop invariant condition is that max is always maximum among the first i elements of array A.

Loop Invariant condition of various algorithms:

Prerequisite: insertion sort, selection sort, quick sort, bubblesort,

Selection Sort:

In selection sort algorithm we find the minimum element from the unsorted part and put it at the beginning.

min_idx = 0

for (i = 0; i < n-1; i++)

{

min_idx = i;

for (j = i+1 to n-1)

if (arr[j] < arr[min_idx])

min_idx = j;

swap(&arr[min_idx], &arr[i]);

}

In the above pseudo code there are two loop invariant condition:

1. In the outer loop, array is sorted for first i elements.

2. In the inner loop, min is always the minimum value in A[i to j].

Insertion Sort:

In insertion sort, loop invariant condition is that the subarray A[0 to i-1] is always sorted.