0
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Ilya Gazman Jan 29 at 20:03
  • $\begingroup$ 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. $\endgroup$ – Ross Millikan Jan 29 at 20:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.