Consider the following algorithm for calculating a number raised to a power. The input is a real number

$x$ and a nonnegative integer $n.$ The output is a real number $r.$

Algorithm $1$ Power $(x,n)$

rlarr$1$;ylarrx;plarrn

while $p>0$ do

if $p$ is odd then

rlarrr$y$

end if

ylarry$y$

plarr${|}_{{?}_{?}}\frac{p}{2_{{?}_{?}}}|$

end while

return $r$

The correctness property for this algorithm is the following:

$r=x^n$

$($a$)$ State the loop invariant for the while loop.

$($b$)$ Prove the correctness of the algorithm using the loop invariant.

$($c$)$ What is the running time of this algorithm? Justify your answer.