$($b$)$ You are given the following algorithm which accepts as input an $\backslash$times $$ square

matrix A and we need to compute C $=$ A

$2=$ AxA where A$[$i$,$ j$]$ is the element in row

i and column j$.$

$1$: procedure MATRIXSQUARED$($A$,$ n$)$

$2$: for i $=1$ to n do

$3$: for j $=1$ to n do

$4$: for k $=1$ to n do

$5$: C$[$i$,$ j$]=$ C$[$i$,$ j$]+($A$[$i$,$ k$]$ A$[$k$,$ j$])$

$6$: end for

$7$: end for

$8$: end for

$9$: return TRUE

$10$: end procedure

$($i$)(3$ points$)$ State the primitive operations and the data structure$($s$)$ to be used

in this algorithm.

$($ii$)(4$ points$)$ Compute the worst$-$case running time T $($n$)$ to output the final

result. Write your answer exactly, without using asymptotic notation.

$($iii$)(2$ points$)$ Write your answer for part$($ii$)$ using $\backslash$Theta $-$notation.