Algorithm to calculate sum of elements of specific range in an array

1
votes

We have an array arr[0 . . . n-1]. We should be able to Find the sum of elements from index l to r where 0 <= l <= r <= n-1.

A simple solution is to run a loop from l to r and calculate sum of elements in given range. The operation takes O(n) time .

Another solution is to create another array and store sum from start to i at the ith index in this array. Sum of a given range can now be calculated in O(1) time.

In the first example the complexity is O(n) understood because it is traversing each element of the array. But in second solution how the complexity is O(1). Please help me to understand this.

2
algorithmdata-structures
O(1) + O(1) = O(1) - Henk Holterman
The second solution spends O(n) time on precalculating cumulative sums, so that sum[i] is the sum of all elements from 0 to i. To find the sum of elements between indices i and j, you only need to fetch sum[i] and sum[j], and subtract them. Accessing array items is O(1), since it involves only a single read from a known location, and 2 * O(1) is still O(1), as @Henk wrote above. - Groo
Thank you all for the reply. Understood the concept now. - Akshaya KAushik

2 Answers

0
votes

The second solution consists of a preprocessing step with O(n) complexity and calculating sum[r] - sum[l-1] that is obviously O(1). The overall complexity is O(n).

The difference between these solutions is the time complexity of the query part. The first solution has O(n) query, second - O(1). And if we have m range queries then the complexity of the first approach would be O(n*m), and complexity of the second - O(n+m) that is much better.

0
votes

The complexity mentioned is about answering query. In first case, you are iterating through l to r which makes it O(n), but in second case, sum[l] = arr[0] + ... + arr[l] and sum[r] = arr[0]+ ... +arr[r]. To get the sum of the elements in the range [l,r] you have to do sum[r]-sum[l-1] where {l>0}, which is just a single operation. That's why the complexity in second case is O(1)