Sunday, 15 September 2013

Runtime of SubArray equalling a sum

Runtime of SubArray equalling a sum

Recently I came across this C code to find the integers in an array
equalling a sum.
int subArraySum(int arr[], int n, int sum)
{
/* Initialize curr_sum as value of first element
and starting point as 0 */
int curr_sum = arr[0], start = 0, i;
/* Add elements one by one to curr_sum and if the curr_sum exceeds the
sum, then remove starting element */
for (i = 1; i <= n; i++)
{
// If curr_sum exceeds the sum, then remove the starting elements
while (curr_sum > sum && start < i-1)
{
curr_sum = curr_sum - arr[start];
start++;
}
// If curr_sum becomes equal to sum, then return true
if (curr_sum == sum)
{
printf ("Sum found between indexes %d and %d", start, i-1);
return 1;
}
// Add this element to curr_sum
if (i < n)
curr_sum = curr_sum + arr[i];
}
// If we reach here, then no subarray
printf("No subarray found");
return 0;
}
My questions the run time of this algorithm is given as O(n) which can be
proved by counting the number of operations performed on every element of
arr[] in worst case. As far I can see it looks like a O(n^2) algorithm.
May be I missed to learn something but can anybody explain how this is
O(n), if at all this is O(n).

No comments:

Post a Comment