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