5. Consider the following basic problem. Youre given an array A consisting of n integers A[1], A[2], . . . , A[n]. Youd 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]. (The value of array entry B[i, j] is left unspecified whenever i j, so it doesnt matter what is output for these values.)

Heres a simple algorithm to solve this problem:

For i=1, 2,...,n For j=i+1, i+2,...,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 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).

(b) For this same function f , show that the running time of the algorithm on an input of size n is also Omega(f(n)). (This shows an asymptotically tight bound of Theta(f (n)) on the running time.)

(c) Although the algorithm you analyzed in parts (a) and (b) is the most natural way to solve the problemafter all, it just iterates through the relevant entries of the array B, filling in a value for eachit contains some highly unnecessary sources of inefficiency. Give a different algorithm to solve this problem, with an asymptotically better running time. In other words, you should design an algorithm with running time O(g(n)), where limn g(n)/f (n) = 0.