UGC NET CSE | December 2018 | Part 2 | Question: 46

Question

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+2^k$

$k=k+1$

end while

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

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

• A. $p=2^k-1$ and $0 \leq k < m$
• B. $p=2^{k+1}-1$ and $0 \leq k < m$
• C. $p=2^k-1$ and $0 \leq k \leq m$
• D. $p=2^{k+1}-1$ and $0 \leq k \leq m$

Comments

mam, why you checking after executing the line p = p + 2$^k$ ?

check before that line tooo...

then p=0,k=0 ==> option c is matching

---

ok, thank u

that means, loop invariant will be executed before any condition will be evaluated

right?

---

before any statement of the loop evaluated

Answer 1

$k=0,p=0$

After $first$ iteration, $p=0+2^0=1,\,k=1$

After $n^{th}$ iteration, $p=2^0+2^1+...+2^{n-1}=2^{n}-1,k=n$

As, the loop will go for $m$ iterations, so, $0\leq k\leq m$

So, $(C)$ should be the answer