Question $1$

Consider the following algorithm:

function : array$)$

let $n$ be the length of $A$

count larr$0$

for i from $0$ to $n-1$ do

for $j$ from $i+1$ to $n-1$ do

if $A[i]A[j]$ then

count larr count $+1$

end if

end for

end for

return count

end function

$($a$)$ Derive a closed$-$form $T(n)$ for the number of array accesses, where $n$ is the length of the input array. Note: Do not consider short$-$circuit evaluation for $T(n).$

$($b$)$ Does the closed$-$form $T(n)$ change if the condition for the if statement is $(A[i])A[j]$ instead?

$($c$)$ Describe the output of the algorithm in a single sentence.

$($d$)$ What is the lowest possible value for count?

$($e$)$ What is the highest possible value for count?