function

pow(n)

k = 1

c = 0

while c < n do

k = 2 k

c = c + 1

end while

return k

end function

(a) Consider the following loop invariant for the while loop: At the beginning of the while loop, we have k = 2c . Prove that the invariant holds by induction.

(b) Assuming that the invariant is true, prove that the invariant implies that the algorithm is correct.

(c) What is the runtime of the algorithm?