# 3Sum complexity

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$$

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.

• How can I convince you otherwise? What tests do I need to do to show that the search for $h_c$ and $h_b$ is not significant? Also does the average case matters here? – Ilya Gazman Jan 29 at 20:03
• So far it sounds like you are linearly stepping through the array looking for $h_c$ and then $h_b$. The bounds you find from $h_a$ are good for reducing the range of search, but you have not explained why they are sufficient to reduce the search space below (some factor times) $n$ for each. – Ross Millikan Jan 29 at 20:12