Glad you liked it! The O(N) time to compute a range sum comes because we are looping through an array. While this particular array has a fixed size, that's true, but if we generalise you'll notice that if we have an array with N items the range sum takes O(N) to compute. Compare this to the prefix sum array, where no matter how big it is, compute time is O(1) because queries array memory access is O(1).
You also need to consider that even though the size of the array is the same, the size of the queries is not. For example, sum of elements m[0] to m[10] is easier to compute than sum of elements from m[11] to m[90] since the first one requires lesser operations.
Very much appreciate this article.
When i was reading the Initial example i was visualizing what the Array would look like.
Sorry but i do not follow the
Time to Compute
formula
given in the Initial example.
A fixed size array (100 possible scores + 1) is populated with # of students with the score used as the position index.
A Range from low to high is given for array indexes of interest.
Wouldn't the notation be more clear using low & high rather than r & l ?
Array memory access is O(1) to get to a start position and value.
Maybe memory access times are not important here.
The number of positions to be visited is (high - low + 1)
If the range is just 1 (high = low)
The total is just O(1) ?
I don't see how O(N = 100) is an invariant here.
Thanks for the article, i need to be more dangerous with structures !
Hi Randy,
Glad you liked it! The O(N) time to compute a range sum comes because we are looping through an array. While this particular array has a fixed size, that's true, but if we generalise you'll notice that if we have an array with N items the range sum takes O(N) to compute. Compare this to the prefix sum array, where no matter how big it is, compute time is O(1) because queries array memory access is O(1).
You also need to consider that even though the size of the array is the same, the size of the queries is not. For example, sum of elements m[0] to m[10] is easier to compute than sum of elements from m[11] to m[90] since the first one requires lesser operations.