You are given an array of n integers A[1..n]. You goal is to compute all the sum

Question

You are given an array of n integers A[1..n]. You goal is to compute all the sums of contiguous subsets of these integers. In other words, your goal is to produce an n-by-n two dimensional array S so that s[I,j] for i_ j, we just set the value of S(i,j) to be NULL.) Consider the following algorithm for this problem. What is a function f(n) such that the running time of this algorithm is theta (f(n) ? Given an algorithm to compute the array S with a faster asymptotic running time than the one in part. To show this, provide a function g(n) such that the running time of your algorithm is o(g(n)) and g(n) is asymptotically better than f(n)=0

Explanation / Answer

Algorithm to Computer Array with a fatser asymptotic running time than the one in part(a)

for i = 1 to n
   for j = i+1 to n
       s[i,j] = s[i,j-1] + A[i,j];
   end
end

Running Time :
for each value of i, the inner loop run from i+1 to n
for i = 1, inner loop run for (n-2) times;
for i = 2, inner loop run for (n-3) times;
for i = 3, inner loop run for (n-4) times;
.
.
.
for i = n, inner loop run for 0 times;
=> (n-2) + (n-3) + (n-4) + (n-5) .... 0
=> ((n-1)*n)/2
=> O(n^2)

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.