3Sum complexity

algorithmscomplex-analysiseuclidean-algorithm

I came up with a solution to the 3-sum problem, but I need your help to understand the complexity of my algorithm.

I store the input in $n$ digits array. My goal is to find $a >= b >= c$ that belongs to the array and their sum is $0$.

  • I sort the array in ascending order for the cost of $O(n\log{n})$,
  • let the smallest element be $min$, I substruct $-min$ from all the elements and change the problem to find $a >= b >= c >= 0$ with the sum of $-3min$, this action cost $O(n)$. Now all the elements are positive
  • Let $h_a$ be the high of $a$ it cannot be larger than $-3min$, so I do a binary search to find the first element smaller or equal to $h_a$, once I find it I update $h_a$ to its value
  • Let $h_b$ be the high of $b$ it cannot be larger than $-3min – h_a$. I do a binary search find the first element smaller or equal to $h_b$ and update $h_b$ with its value
  • Let $h_c$ be the high of $c$ it cannot be larger than $-3min – h_a – h_b$. I do a binary search to find the first element larger or equal to $h_c$ if I find a match, then the problem is solved, in case of a higher value I assign it to $h_c$ and update $h_b$.
    Since no match was found for the current selection of $h_a$ and $h_b$, they need to be updated, and since I would like to test all the options for $h_b$ before updating $h_a$, I update $h_b$ first. Its new max value is $$h_B = -3min -h_a – h_c$$
  • With the new value of $h_b$ I recalculate the value of $h_c$ as mentioned above, I run this loop until a match is found or no options left
  • Once all the values of $h_b$ were eliminated, I updated the value of $h_a$ for the next smallest number in the array and recalculated $h_b$ and repeat the above loop

Once the array was sorted and shifted the loop starts testing all the options for $h_a$ and for each option it does a binary search to find $h_b$ and $h_c$

The question is does the binary search considered to be $O(n)$ in such case the performance of this algorithm will be $O(n^2)$, or it's considered to be $O(\log{n})$ in such case the algorithm is $O(n\log{n})$. Note that the binary search is not on the entire array but between the indexes of $h_c$ and $h_b$.

Here is a small example to demonstrate it. Consider the below input:

62, 109, -460, 165, 186, -809, -10, -401, -171, 377, 519, -211, -660, -563, -335, -740, -563, 269, 593, 983

After sorting and shifting it turnes to 

0, 69, 149, 246, 246, 349, 408, 474, 598, 638, 799, 871, 918, 974, 995, 1078, 1186, 1328, 1402, 1792

$$min = -809$$

  • $h_a$ is found to be $1792$, but there is no option for $h_b$
  • $h_a$ is found to be $1402$, but there is no option for $h_b$
  • $h_a$ is found to be $1328$, but there is no option for $h_b$
  • $h_a$ is found to be $1186$, $h_b$ is $995$, $h_c$ is $246$

The problem is solved after 4 steps

$$1186 + 995 + 246 = -3(-809)$$
$$377+ 186 -563 = 0$$

Best Answer

A binary search through $n$ items just takes $\log_2 n$ checks. After that many you have either found the item you are looking for or have shown that it is not there.

You have not demonstrated that your algorithm is $O(n \log n)$ because the search for $h_c$ and $h_b$ might each take a significant fraction of $n$ operations.

Related Question