You are given an array A (of size n) of integers. The goal is to construct a 2-d

Question

You are given an array A (of size n) of integers. The goal is to construct a 2-dimensional array D (of size n × n) such that whenever i < j, D[i, j] is:

alil+ali1+aj] D[i, can be arbitrary when i j (a) Consider the following algorithm that creates D from A For i in the range [1, 2, ..., n-1] I For j in the range [i+1, i+2, ...n] f Compute the sum of a[i], a[i+1], Store the sum in D[i, j] alj] Derive the run time of the above algorithm and express the run time in Big-O notation (b) Give an algorithm for this problem that is asymptotically more efficient than the above algorithm. Derive the asymptotic run-time of your algorithm. Part of the grade depends on the runtime of your algorithm

Explanation / Answer

a. Given algorithm

for i in the range [1 n-1]
   for j in the range [i+1,n]
       D[i][j] = sum(a[i] to a[j])
      
Here we're using 2 loops, for each iteration in the inner loop, we are calculating the sum is O(N) time. So, total complexity can be given as
O(N)*O(N)*O(N) = O(N^3)

This is very slow

b.

We have an array A
Now , let's build another array P, such that P[i] denotes sum of all elements in the array A from 1 to i. This is known as prefix sum.

for i in range[1 n]
   P[i] = P[i-1] + A[i]
  
Now P[i] contains prefix sum We can observe an important point that sum of elements from i to j can be given by P[j]-P[i-1]. Since P stores prefix sums, P[j]-P[i-1] gives sum of the elemetns in the array from i to j

for i in range [1 n]
   for j in range[i+1 n]
       D[i][j] = P[j]-P[i-1]

      
Time complexity for building prefix sums is O(N)
Time complexity for running two loops is O(N^2) . So, total time complexity is O(N)+O(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.