547 views
1 votes
1 votes
what is significance of loop Invariant?

when we use a loop in an algo we check it , if it properly runs then fix it in that, then why do check separately loop invariant ?

1 Answer

Best answer
3 votes
3 votes

In simple words, a loop invariant is some predicate (condition) that holds for every iteration of the loop. For example, let's look at a simple for loop that looks like this:

 

int j = 9;
for(int i=0; i<10; i++)  
  j--;

 

In this example it is true (for every iteration) that i + j == 9. A weaker invariant that is also true is that i >= 0 && i <= 10.

 

Further Read: https://www.cs.miami.edu/home/burt/learning/Math120.1/Notes/LoopInvar.html
selected by

Related questions

0 votes
0 votes
1 answer
1
tusharb asked Feb 18, 2022
654 views
As we know the time complexity of solving the greedy knapsack algorithm depends mainly on the sorting algorithm used, Can we use counting sort as the sorting algorithm to...
1 votes
1 votes
1 answer
2
kumar.dilip asked Jan 19, 2019
664 views
The average no. of comparisons performed by the merge sort algorithm, in merging 2 sorted lists of length 2 is___________.Ans: $\frac{8}{3}$
0 votes
0 votes
1 answer
3
Prince Sindhiya asked Jan 19, 2019
323 views
When relative ordering of equal keys is preserved after sorting then it is called stable. Quick sort and heap sort is not a stable sorting algorithm . Doubt -IS Select...