Question

I am trying to calculate the runtime complexity of a function that does not have fixed size input, but uses several helper methods that do have fixed size input. I was unsure of how to include the helper methods in my calculations.

If I have an array with a fixed size of 32 indices, and I have a function that sums up the elements in that array, will that function be O(n), or O(1)? I think that a function that sums up the elements of an array is O(n) because each element of an n-length array must be visited, but if the function only sums up arrays of length 32, is it still O(n)?

Answer 1

There are some things to consider here.

Conceptually, an algorithm that iterates once over the input array has runtime ?(n) (and O(n) if it does constant-time work per element), n being the size of the array.

In application, if the algorithm is only ever called with arrays of length n?n0 for some constant n0, you may treat the used time as O(n)?O(n0)=O(1). Note that the n here is probably not the one you use for your whole algorithm!

In practice, every algorithm runs constant time as real computers have finite memory. This is not an interesting model in the sense that it does not help to differentiate between algorithms that do behave very differently in practice, so we don't use it.

You may be interested in some of our reference questions on asymptotics, runtime analysis and the time used by arithmetic operations.

Answer 2

#include<iostream>

int subArraySum(int arr[], int n, int sum)

{

int curr_sum, i, j;

    for (i = 0; i < n; i++)

    {

        curr_sum = arr[i];

}

for (j = i+1; j <= n; j++)

        {

            if (curr_sum == sum)

            {

                printf ("Sum found between indexes %d and %d", i, j-1);

                return 1;

            }

            if (curr_sum > sum || j == n)

                break;

           curr_sum = curr_sum + arr[j];

        }

    }

printf("No subarray found");

    return 0;

}