Mystery(n: integer>0)

1 temp=1 2 for i = 1 to n do 3 temp=temp*1 4 return temp

(a) What does this algorithm compute?

(b) Write down the loop invariant for the loop in steps 2-3.

(c) Initialization: Prove that your loop invariant is true before the first iteration of the loop:

(d) Maintenance: Prove that if the loop invariant is true before any (say, the kth) iteration, show also that it remains true before the next(k+1 th) iteration:

(e) Termination: The two proofs above imply that the loop invariant must be true, show that the algorithm computes what you said it does in part(a):