4) Analyze the following algorithm to compute xn for a positive integer n.

Initialize power to 1 and sqr to x

Loop

while n > 1

if n is odd

Multiply power by sqr

Halve n

Square sqr

Return power * x

a) Determine its order as a function of n.

b) Prove the algorithm is correct. Give reasons for your steps.