Consider the sorting algorithm shown below, which is called bubblesort.

Algorithm $1\mathrm{.}16$ bubblesort

Input: An array A$[1..$n$]$ of n elements.

Output: A$[1..$n$]$ sorted in nondecreasing order.

$1.$ i$1$; sorted $$ false

$2.$ while i $<=$ n $1$ and not sorted

$3.$ sorted $$ true

$4.$ for j$$ n downto i $+1$

$5.$ if A$[$j$]<$ A$[$j $1]$ then

$6.$ interchange A$[$j$]$ and A$[$j $1]$

$7.$ sorted $$ false

$8.$ end if

$9.$ end for

$10.$ i$$ i $+1$

$11.$ end while

$($a$)$ What is the minimum number of element comparisons performed

by the algorithm? When is this minimum achieved?

$($b$)$ What is the maximum number of element comparisons performed

by the algorithm? When is this maximum achieved?

$($c$)$ What is the minimum number of element assignments performed

by the algorithm? When is this minimum achieved?

$($d$)$ What is the maximum number of element assignments performed

by the algorithm? When is this maximum achieved?

$($e$)$ Express the running time of Algorithm bubblesort in terms of the

O and $$ notations.

$($f$)$ Can the running time of the algorithm be expressed in terms of the

$\backslash$Theta $-$notation? Explain.