Click here to Skip to main content
15,896,726 members
Please Sign up or sign in to vote.
1.00/5 (1 vote)
See more:
Is there any way to sum up an array elemnets from position A to B in O(1) time in C?

Lets say we have an array and we want to find the some of elemnts from A to B. The complexity is O(n).

C
int sum_array(int* array,int start, int end)
{
    int i = start;
    int res = 0;
   while (i != end) {
       res += array[i];
       i++;
   }
    return res;
}

int main() {
    int array[10] = { 2,6,9,4,2,64,5,9,54,3 };
    int A = 3;
    int B = 8;
    
    int Sum = sum_array(array,A,B);
    
    //sum is 138!
}




Is there any way to make it O(1)?
Posted
Updated 5-Feb-15 4:32am
v3
Comments
Leo Chapiro 5-Feb-15 10:24am    
What do you mean by that, dude? Show your source code please!
[no name] 5-Feb-15 10:26am    
ok
Leo Chapiro 5-Feb-15 10:37am    
So do you want to find an element or to sum up from ... till? What is exactly the question?
[no name] 5-Feb-15 10:42am    
The question very at the end ...Is there any way to make it O(1)?
[no name] 5-Feb-15 10:43am    
well you both have right. I wan to sum from...to and also that in O(1)

1 solution

For an array of random numbers you can't achieve constant complexity O(1) but rather O(n).
If you have an array of a number sequence (1, 2, 3, 4, 5 ...) the sum can be computed with O(1).
 
Share this answer
 
Comments
[no name] 5-Feb-15 10:51am    
what do you mean with number sequence?
CPallini 5-Feb-15 11:49am    
Exactly, 5.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900