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 ? Algorithms algorithms sorting + – afroze asked Nov 4, 2021 afroze 547 views answer comment Share Follow See all 7 Comments See all 7 7 Comments reply Show 4 previous comments Awe111 commented Nov 5, 2021 reply Follow Share @afroze Invariant in this case means a condition that must be true at a certain point in every loop iteration… In contract programming, an invariant is a condition that must be true (by contract) before and after any public method is called... 0 votes 0 votes afroze commented Nov 5, 2021 reply Follow Share I understood what u said but I have a doubt in this weak loop invariant means algo may or may not be true 0 votes 0 votes Awe111 commented Nov 6, 2021 reply Follow Share @afroze I understood what u said but I have a doubt in this weak loop invariant means algo may ... @@ https://gateoverflow.in/504/Gate-cse-1991-question-1-vi 1 votes 1 votes Please log in or register to add a comment.
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 Vishal_kumar98 answered Nov 4, 2021 selected Nov 4, 2021 by afroze Vishal_kumar98 comment Share Follow See 1 comment See all 1 1 comment reply afroze commented Nov 4, 2021 reply Follow Share thanks 👍 0 votes 0 votes Please log in or register to add a comment.