Na$$veSort $($A$)$

$1$ for $i=A.$ length downto $2$

for $j=i-1$ downto $1$

if $A[j]A[i]A[1]A[2]dotsA[n],n=2-4T(n)T(n)A[i]$

exchange $A[j]$ with $A[i]$

Part I $(45$ points$)$ Correctness

$a.$ Let A denote the output $of$ NaiveSort $(A).To$ prove that $NaveSortis$ correct, $we$ need $to$ prove that $it$ terminates and that

$A[1]A[2]dotsA[n],$

where $n=A.$length. $In$ order $to$ show that $NaveSort$ actually sorts, what else $dowe$ need $to$ prove?

Answer the next two questions $b.$ and $c.to$ prove inequality $(2\mathrm{.}3).$

$b.(20$ points$)$ State precisely a loop invariant for the for loop $in$ lines $2-4,$ and prove that this loop invariant holds. The loop invariant must $be$ useful, $i.e.,it$ must help prove Property $2\mathrm{.}3.$ Your proof should use the structure $of$ the loop invariant proof presented $in$ this chapter:

$(5$ points$)$ Loop invariant $is$: answer here $.....$

$(3$ points$)$ Initialization: answer here $.....$

$(8$ points$)$ Maintenance: answer here $.....$

$(4$ points$)$ Termination: answer here $.....$

$c.$ Using the termination condition $of$ the loop invariant proved $in$ part $(b),$ state a loop invariant for the for loop $in$ lines $1-4$ that will help you $to$ prove inequality $(2\mathrm{.}3).$ Your proof should use the structure $of$ the loop invariant proof presented $in$ this chapter:

$(6$ points$)$ Loop invariant $is$: answer here $.....$

$(4$ points$)$ Initialization: answer here $.....$

$(10$ points$)$ Maintenance: answer here $.....$

$(5$ points$)$ Termination: answer here $.....$

Part $II(45$ points$)$ Running Time $ofNaveSort$

$a.(2$ points$)$ What $is$ the input size? answer here $.....$

$b.(3$ points$)$ What $is$ the operation that you will count? answer here

$c.(40$ points$)$ Let $T(n)be$ the running time $ofNaveSort.$ Derive the asymptotic bound for $T(n).$