October 20, 2023
October 20, 2023
October 20, 2023
###### GATE 2014 [Set-1]
October 20, 2023
 Question 195

Consider the following pseudo-code fragment, where m is a non-negative integer that has been initialized:

```     p = 0;
k = 0;
while(k < m)
p = p + 2k;
k = k + 1;
end while```

Which of the following is a loop invariant for the while statement?

(Note: a loop variant for a while statement is an assertion that is true each time guard is evaluated during the execution of the while statement).

Options:

 A p = 2k – 1 and 0≤k
Question 195 Explanation:
For k=0, P = 0+20 = 1
k=1, P = 1+21 = 3
k=2, P = 3+22 = 7
k=3, P = 7+23 = 15
Only the option-3 satisfied to the loop variant.
Ex: m=2, The loop will execute for 3 times for k value is 0,1 and 2.
Then options-3 gives P=1, P=3 and P=7 for the k values 0,1 and respectively.
Question 195 Explanation:
For k=0, P = 0+20 = 1
k=1, P = 1+21 = 3
k=2, P = 3+22 = 7
k=3, P = 7+23 = 15
Only the option-3 satisfied to the loop variant.
Ex: m=2, The loop will execute for 3 times for k value is 0,1 and 2.
Then options-3 gives P=1, P=3 and P=7 for the k values 0,1 and respectively.