Look at the image below for the LARGEST algorithm and all the questions.

This homework assignment is about determining the run time of a simple array algorithm, and about proving its correctness. It uses techniques like those used in the Cormen text for the procedure INSERTION$-$SORT.

The procedure LARGEST has parameters A and $n,$ where $A$ is an array of integers, and $n$ is $A\text{'}$s length, which is greater than $0.A\text{'}$s indexes run from $1$ to $n.$ Each element of $A$ is greater than $0,$ and mays

more than once. LARGEST returns a maximum element chosen from $A.$

$1$a$.(5$ points.$)$ What is the cost and count of each line in LARGEST? A line's cost is its run time. Its count is the number of times it is executed. Replace the question marks in the table shown above.

$1$b$.(5$ points.$)$ Let $T(n)$ be the run time of LARGEST when it is called with an array of length $n.$ What is $T(n)$ in the best case? Use your answer from $1$a to define $T(n)$ as an expression in closed form. Do not use $O,\backslash$Omega $,$

or $$ notation. Briefly explain your answer.

$1$c$.(5$ points.$)$ What is $T(n)$ in the worst case? Use your answer from $1$a to define $T(n)$ as an expression in closed form. Your answer may be different from that of $1b.$ Do not use $O,,$ or $$ notation. Briefly explain

your answer.

In questions $2$a through $2$d$,$ use a loop invariant to prove that LARGEST is correct. Your invariant, and your proof, may be written in mathematics, in English, or in a mixture of the two.

$2$a$.(5$ points.$)$ Show a loop invariant for LARGEST. Hint: Your invariant may optionally use logical connectives like $,,,->,$ etc.

$2$b$.(5$ points.$)$ Prove that your invariant from $2$a is true at initialization.

$2$c$.(10$ points.$)$ Prove that your invariant from $2$ a is true during maintenance.

$2$d$.(5$ points.$)$ Prove that your invariant from $2$a shows that LARGEST is correct at termination.