The following algorithms were given for computing the nth power of a positive integer.

(a) Use induction to prove that each of these algorithms is correct.

def pow(a, n):
if n == 0:
return 1
return pow(a, n-1) * a
end

(b) Hint: you need cases due to last two if-statements.

def pow(a, n):
if n == 0:
return 1
x = pow(a, floor(n/2))
if n % 2 == 0:
return x * x
if n % 2 != 0:
return a * x * x
end