$16.$ Kleinberg, Jon. Algorithm Design $($p$.68,$ q$.6).$ You$$re given an array A consisting of n integers. You$$d

like to output a two$-$dimensional n$-$by$-$n array B in which B$[$i$,$ j$]($for i $<$ j$)$ contains the sum of array

entries A$[$i$]$ through A$[$j$]$ that is$,$ the sum A$[$i$]+$ A$[$i $+1]+...+$ A$[$j$].($Whenever i $>=$ j$,$ it doesn$$t

matter what is output for B$[$i$,$ j$].)$ Here$$s a simple algorithm to solve this problem.

for i $=1$ to n

for j $=$ i $+1$ to n

add up array entries A $[$ i $]$ through A $[$ j $]$

store the result in B $[$i $,$ j $]$

endfor

endfor

$($a$)$ For some function f that you should choose, give a tight bound of the form O$($f $($n$))$ on the running

time of this algorithm on an input of size n $($i$.$e$.,$ a bound on the number of operations performed

by the algorithm$).$