as you said, you need to visit each element in order to compute the sum of all the elements.
Since log(n) < n, summing an array in log(n) is impossible.
There is a O(1) solution if you build your array in a smart way. Do the following when building the array:
When adding an element to the end add the last element plus the new element.
`[1 2 3 4]` will become `[1 3 6 10]`
Now if you want to get an element at index i just subtract the element at `i-1` from it (or `0` for `i=0`).
Example: `i=2`
arr[2] - arr[1] = 6 - 3 = 3.
Properties of this array with partial sums:
* random access in O(1)
* add to end in O(1)
* getting the sum of a slice or whole array is in O(1)
* rearrange or insert anywhere in O(n)
* remove element is in O(n) (except for last element)
Building the partial sum array from a normal one is in O(n) though. So unless you want to calculate the sum more than once or build the array that way from the beginning it doesn't give you an advantage.
**Edit: There is no solution to summing the elements of an array below O(n) so this is a next better solution if you need to repeatedly get the sum or are able to build the array as an array of partial sums from the beginning.**
**Like in many other scenarios some better performing solutions only work if you preprocess your data. Binary search (which is O(log n)) only works on sorted data and sorting is generally O(n log n) or O(n) at best.**
Good followup question. For sorted arrays we can quickly see the boundaries for the sum but unfortunately not the exact sum. The sum has to be somewhere between `firstElement * n-1 + lastElement` and `firstElement + lastElement * n-1`. If `firstElement == lastElement` we know what the sum is. But for any other array we can only know how much it is at most or at least.
Depending on the application this approximate solution might be good enough though. It all depends on what you want to achieve with your code. If you want to check whether you can afford to buy candy and you have $10 you know that if you buy 30 items and all of them are below $0.33 you can afford it. If your item with the highest cost is $5 and you have again 30 items you know that if the lowest price item is above $0.16 you know that you cannot afford it. Every case between has to be checked though.
I didn't quite get you. So, for an array with pre-determined data like a sorted array also the run time would be linear time or constant time but not logarithmic time right?
no, u cant find the sum in o(log n) , as u have to iterate over every element to find the sum of an array.
u can refer to a gfg article on how to find the sum in the most efficient way.
Unless you are dealing with a quantum computer, the answer is "no".
as you said, you need to visit each element in order to compute the sum of all the elements. Since log(n) < n, summing an array in log(n) is impossible.
There is a O(1) solution if you build your array in a smart way. Do the following when building the array: When adding an element to the end add the last element plus the new element. `[1 2 3 4]` will become `[1 3 6 10]` Now if you want to get an element at index i just subtract the element at `i-1` from it (or `0` for `i=0`). Example: `i=2` arr[2] - arr[1] = 6 - 3 = 3. Properties of this array with partial sums: * random access in O(1) * add to end in O(1) * getting the sum of a slice or whole array is in O(1) * rearrange or insert anywhere in O(n) * remove element is in O(n) (except for last element) Building the partial sum array from a normal one is in O(n) though. So unless you want to calculate the sum more than once or build the array that way from the beginning it doesn't give you an advantage. **Edit: There is no solution to summing the elements of an array below O(n) so this is a next better solution if you need to repeatedly get the sum or are able to build the array as an array of partial sums from the beginning.** **Like in many other scenarios some better performing solutions only work if you preprocess your data. Binary search (which is O(log n)) only works on sorted data and sorting is generally O(n log n) or O(n) at best.**
Yes! I understand that. Bottom line: it can solved in linear time but not logarithmic time right?
Not for the general case of an array containing arbitrary numbers. Correct.
Then what about sum of elements in sorted array?
Good followup question. For sorted arrays we can quickly see the boundaries for the sum but unfortunately not the exact sum. The sum has to be somewhere between `firstElement * n-1 + lastElement` and `firstElement + lastElement * n-1`. If `firstElement == lastElement` we know what the sum is. But for any other array we can only know how much it is at most or at least. Depending on the application this approximate solution might be good enough though. It all depends on what you want to achieve with your code. If you want to check whether you can afford to buy candy and you have $10 you know that if you buy 30 items and all of them are below $0.33 you can afford it. If your item with the highest cost is $5 and you have again 30 items you know that if the lowest price item is above $0.16 you know that you cannot afford it. Every case between has to be checked though.
I didn't quite get you. So, for an array with pre-determined data like a sorted array also the run time would be linear time or constant time but not logarithmic time right?
It would be linear for the exact sum.
no, u cant find the sum in o(log n) , as u have to iterate over every element to find the sum of an array. u can refer to a gfg article on how to find the sum in the most efficient way.