World's most popular travel blog for travel bloggers.

[Solved]: Big Omega of 3-Sum Algorithm

, , No Comments
Problem Detail: 

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?

Asked By : Dom Farolino

Answered By : Yuval Filmus

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/35612

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback