what is the time complexity of the three sum algorithm

Question

it is a function to find three numbers in array whoose sum is equal to zero.

//helper function
bool isPresent(int*arr, int size, int index, int num)
{
    for (int i = index; i < size; i++)
    {
        if (arr[i] == num)
            return true;
    }
    return false;
}
bool threesum(int*arr,int size)
{
    int i = 0, j = 1;
    int sum = arr[i] + arr[j];
    while (i < size-2)
    {
        if (isPresent(arr, size, j + 1, -sum) == true)
        {
            cout << arr[i] << " + " << arr[j] << " + " << -sum << '\n';
            return true;
        }
        if (j == size)
        {
            i++;
            j = i + 1;
        }
        j++;
        sum = arr[i] + arr[j];
    }
    return false;
}

there are two loops in the threeSum function one is while up to size of array second one is isPresent whose time complexity is O(n) so the time complexity of threesum function should be O(n^2) but while loop iterates more time because of j, So is the time complexity of threesum function is O(n^2) or O(n^3)?

Answer 1

It's O(n^3). Think how i is changing with j. Suppose, n = 10. At first i = 0, j = 1. i won't become 1, until j = 10, and then after these steps, again i = 1, j = 2. It's like writing two for loops like this:

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

Answer 2

The naïve approach is O(N³).

To see which sums of three are 0 all sums are computed and there are N * (N-1) * (N-2) / 4 different sums.

But you can easily improve on that bound by first indexing the numbers and then computing all the sums of pairs, storing them in a hash table and then lookup if the negative of the sums exists and test if its components have not already been used in computing the sum. This gives O(N²).

https://en.wikipedia.org/wiki/3SUM

bool threesum(const vector<int>& numbers){
  std::unordered_map<int,size_t> index;
  for (size_t i=0;i!=numbers.size();++i) {
    index.insert({numbers[i],i});
  }
  for (size_t i=0;i!=numbers.size();++i) {
    for (size_t j=i+1;j!=numbers.size();++j) {
      const int n = -(numbers[i]+numbers[j]); 
      if (index.count(n)) {
        if (index[n]==i) continue;
        if (index[n]==j) continue;
        return true; 
      }
    }
  }
  return false;
}