ComputeSumLowerTri angular $(L,n)$

inputs: $L$ is an $nn$ matrix. $n$ is the dimension of the matrix

output: a real number equal to

sum $=0$

for $\frac{i}{m}=n$ to $1$

psum $=0$

for j $=1$ to $\frac{i}{m}$

Dsum $=$ psum $,$

sum $=$ sum $+$psum

return sum

All the questions in this exercise are related to the ComputeSumLowerTriangular $($Lin $n)$

algorithm. The objective of this exercise is to explore whether the asymptotic time complexity

will change if we count different "actions".

A$)(40$ points$)$ Comparison Action $($Lines $2$ and $4).$

In this case, we count the total number of comparisons performed by the "for loops statements" $($Lines $2$ and $4$

only$).$ Answer the following questions to determine the total number of comparisons performed by the algorithm.

a$.(2$ points$)$ How many comparisons in total are performed by the "for loop" statement in Line $2$

during the execution of the algorithm? $($See on the appendix how Student $3$ gets full credit$)$

answer here $.....$

b$.(20$ points$)$ Let us call $t_i$ the number of comparisons performed by the inner "for loop" in Line

$4$ for a given value of $j.$ Fill in this table $($Justify how you find $t_i$ using exactly the same steps

and sentence pattern shown below for $j=1)$:

c$.(8$ points$)$ Based on b$,$ express the total number of comparisons performed by the inner "for

loop" in Line $4$ only during the execution of the algorithm. $($See how Student $3$ gets full credit$)$

answer here $...$

d$.(8$ points$)$ Express the function $f_c(n)$ that represents the overall total number of comparisons

performed by the "for loops" statements in Lines $2$ and $4$ during the execution of the algorithm.

$($See how Student $3$ gets full credit$)$

answer here $...$

e$.(2$ point$)$ The function $f_c(n)$ grows like

credit$)$