3sum algorithm complexity

Question

This code finds if in a sorted array there are three numbers that add up to a given sum, but I'm not sure how to calculate its time complexity. Would love your input and ideas on how to improve it as well.

Note that the for loop can reset itself within the loop.

/* function to find if there are 3 values in the 
sorted array that sum up to a given sum */
int IsSumOf3( int arr[], size_t size, int sum)
{
  int right, left, third;
  right = size-1;
  left = 0;
  while(arr[right] > sum && right > 1)
  {
      --right;
  }
  if(right == 1)
  {
      printf("returned false on right == 1 \n");
      return 0;
  }

  for(third = left+1; third < right; ++third)
  {
      int localSum = arr[right]+ arr[left]+ arr[third];
      if(localSum == sum)
      {
          printf("right |%d|, left |%d|, third |%d|\n",arr[right], arr[left], arr[third]);
          return 1;
      }
      if(localSum > sum)
      {
         --right;
         left = 0;
         third = left;
      }
      if(third+1 == right)
      {
          ++left;
          third = left;
      }
  }
  printf("returned false on exit\n");
  return 0;
}

int main()
{

    int A[] = { 1, 4, 6, 8, 10, 46 };

    IsSumOf3(A,6, 22);
    IsSumOf3(A,6, 11);
    IsSumOf3(A,6, 100);
    IsSumOf3(A,6, 3);

    return 0 ;
}

Answer 1

First, I suggest you comment your code: it would be easier for people here to help you. I also suggest you keep it simple: the first approach should be to build a list of the sum of 2 numbers where the sum is lower than the expected result, then try to find the third element for each value of the 2-values-sum list.

Your algorithm runs through the array until it finds a valid result. At each iteration, if there's no valid result there's one value (left or right) that is not being considered anymore. Iterations in the worst case for an array of N elements are:

N + (N-1) + (N-2) ... + 2 + 1 = N * N/2

Finally, the complexity is O(N^2).

P.S.: notice that counting the case where left = right = third has no impact on the complexity, so to make the calculation easier I just kept it into consideration.

Answer 2

You just go through the array, there is no nested loop of recursive call, so O(n)

Ok now I read the context, yes is late ^^

Or course the worst case is when the values are not sorted because you have to look at up all the values, so N^3. Here the array is sorted.

But you only use a loop, and even you restart it it seemed magical ... too magical, sorry but that doesn't work, you do not find a solution with for instance the vector { 4, 6, 11, 12, 14, 19 } and the expected sum 36, but 6+11+19==36

I do not answer about the complexity, L.C. does, but is the complexity relevant while the algorithm doesn't work ? Just do return 0; having the complexity O(1) ^^

---

P.S. because I had a doubt I used the brutal force to check

#include <stdio.h>
#include <time.h>
#include <stdlib.h>

/* function to find if there are 3 values in the 
sorted array that sum up to a given sum */
int IsSumOf3( int arr[], size_t size, int sum)
{
  int right, left, third;
  right = size-1;
  left = 0;
  while(arr[right] > sum && right > 1)
  {
      --right;
  }
  if(right == 1)
  {
      /*printf("returned false on right == 1 \n");*/
      return 0;
  }

  for(third = left+1; third < right; ++third)
  {
      int localSum = arr[right]+ arr[left]+ arr[third];
      if(localSum == sum)
      {
      /*printf("right |%d|, left |%d|, third |%d|\n",arr[right], arr[left], arr[third]);*/
          return 1;
      }
      if(localSum > sum)
      {
         --right;
         left = 0;
         third = left;
      }
      if(third+1 == right)
      {
          ++left;
          third = left;
      }
  }
  /*printf("returned false on exit\n");*/
  return 0;
}

int brutal(int arr[], size_t size, int sum)
{
  int i,j,k;

  for (i = 0; i != size - 2; ++i) {
    for (j = i+1; j != size -1; ++j) {
      for (k = j+1; k != size; ++k) {
        if ((arr[i] + arr[j] + arr[k]) == sum) {
          /*printf("%d %d %d\n", arr[i], arr[j], arr[k]);*/
          return 1;
        }
      }
    }
  }

  return 0;
}

int main()
{
#define N 6

  int a[N];

  srand(time(NULL));

  for (;;) {
    int i;

    a[0] = rand() % N;

    for (i = 1; i != N; ++i) {
      a[i] = a[i - 1] + (rand() % (N - 1)) + 1; /* suppose must not be equals */
    }

    for (i = a[N-1] + a[N-2] + a[N-3] + 1; i != 0; i -= 1) {
      if (IsSumOf3(a, N, i) != brutal(a, N, i)) {
        int j;

        for (j = 0; j != N; j++)
          printf("%d ", a[j]);
        printf(" / %d\n", i);
        return 0;
      }
    }
  }

  return 0 ;
}