Exercise 2.6. Consider the following basic problem. You’re given an array A consisting of n integers A[1], A[2], …, A[n]. 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]. (the value of array entry B[i, j] is left unspecified whenever i >= j, so it doesn’t matter what is output for these values.)

Here’s 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 for 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).
Solution a): when we looked at the algorithm, the first loop make “n” times run. The second loop runs “n” times too. The summation is over at most n elements. All other operations are constant time. We can say that total time is O(n3).



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

Solution b): think about the first n/3 iterations of outer loop for lower bound, In this algorithm, the inner loops has to run at least 2n/3 times for each of the iterations. Number of elements to be added for these inner loop iterations is at least n/3. Therefore (n/3)3 = 1/27n3 addition operations. Consequence the algorithm is Ω(n3).



c. Although the algorithm you analyzed in parts (a) and (b) is the most natural way to solve the problem–after all, it just iterates through the relevant entries of the array B, filling in a value for each–it contains some highly unnecessary sources of inefficiency. Give a different algorithm to solve the problem, with an asymptotically better running time. In other words, you should design an algorithm with running time O(g(n)), where lim_n->infinity(g(n) / f(n)) = 0
Solution c):
currentSum = 0;
for i=1,2,….,n
currentSum = A[i]; //assign a new variable currentSum to A[i] in each iteration of i.
for j=i+1,i+2,….,n
currentSum = currentSum + A[j] // for each iteration of j, store the current sum of A[i] to A[j] each time.
Store the current sum in B[i,j]
Endfor
Endfor

The operation of adding A[j] to the current sum can be done in constant time, so now the inner loop has a constant time. Consequence, the total running time is O(n2).