The following algorithm performs an insertion sort on an array of $n$ numerical elements:

$($a$)$ Identify a suitable measure of input size and the elementary operations in this algorithm.

$($b$)$ Identify the worst$-$case scenario for the running time of the algorithm, and hence write down a suitable

sum expression for its worst$-$case time complexity.

$($c$)$ Solve this sum and simplify your answer using big$-O$ notation$\mathrm{.}3.$ The following algorithm performs an insertion sort on an array of n numerical elements:

Algorithm: InsertionSort A$[0...$ n $1]$

$//$ Sorts the elements of array A into ascending order for i $=1$ to n $1$ do

$//$ Sort A$[0...$i$]$ by moving A$[$i$]$ to correct position j :$=$ i ;

while j $>0$ do

if A$[$j $1]>$ A$[$j$]$ then swap$($A$[$j $1],$ A$[$j$])$ ;

j :$=$ j $1$ ; return true;

$($a$)$ Identify a suitable measure of input size and the elementary operations in this algorithm.

$($b$)$ Identify the worst$-$case scenario for the running time of the algorithm, and hence write down a suitable sum expression for its worst$-$case time complexity.

$($c$)$ Solve this sum and simplify your answer using big$-$O notation.