2
$\begingroup$

An optimized algorithm for the 3-sum problem with an input array N has O(N^2logN) however I read that the Big Omega for this algorithm could be Omega(N) because you have to touch all entries once. But to me this doesn't make sense.

If you have to perform the 3-sum operation on the entire array, wouldn't Big-O and Big-Omega be the same because regardless of the results the algorithm has to perform the same operations on the entire array?

$\endgroup$
  • $\begingroup$ In this case, Big-O is an upper bound on the complexity of a specific algorithm (and so also an upper bound on the complexity of the problem), while Big-Omega is a lower bound on the complexity of the problem (and so also a lower bound on the complexity of any algorithm for the problem). $\endgroup$ – Yuval Filmus Dec 23 '14 at 6:06
1
$\begingroup$

We don't know what the best complexity for the 3SUM problem is. First of all, we can improve on your $O(N^2\log N)$ algorithm to an $O(N^2)$ algorithm by carefully scanning the two arrays in tandem, thus obviating the binary search. Until very recently, it had been conjectured that there is a corresponding $\Omega(N^2)$ lower bound, and on this basis the complexity of many other problems, especially in computational geometry, had been "determined". However, very recently Grønlund and Pettie gave an $O(N^2/(\log N/\log\log N)^{2/3})$ algorithm, so we know that the $O(N^2)$ algorithm is not optimal. It is still conjectured that 3SUM requires $\Omega(N^{2-\epsilon})$ time for every $\epsilon > 0$.

$\endgroup$
  • $\begingroup$ Very helpful. This makes sense, thanks. $\endgroup$ – Dominic Farolino Dec 23 '14 at 7:14

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