$]$ How can you modify any sorting algorithm to have a good best$-$case running time?

$3.[20$ points$]$ Use a loop invariant to prove that the following algorithm computes a raised to the power of

n:

Exp$($a$,$ n$)$

$\{$

i$1$

pow $1$

while $($ i $<=$ n $)$

$\{$

pow $$pow$*$a

i$$i $+1$

$\}$

return pow

$\}$

Have to prove that pow $=$ ai$-1$

is a loop invariant for the while loop