3-SUM Problem Bounds

Given three arrays $A$,$B$, and $C$, each containing $n$ positive integers. That is, $$A = [a_{1},a_{2},\ldots, a_{n}]$$ $$B = [b_{1},b_{2},\ldots, b_{n}]$$ $$C = [c_{1},c_{2},\ldots, c_{n}]$$ where $a_{i}, b_{j}, c_{k} \epsilon \mathbb{Z}^{+}.$

We need to determine whether any triple such that $$a_{i} + b_{j} = c_{k}$$ exists or not.

Upper Bound: 

Using brute force comparison: $$for \hspace{2 mm} i=1,n$$ $$\hspace{5 mm}for \hspace{2 mm} j=1,n$$ $$\hspace{7 mm}for \hspace{2 mm} j=1,n$$ $$\hspace{12 mm} check\hspace{2 mm} if \hspace{2 mm}$a_{i} + b_{j} = c_{k}$$ it would take at most $n^{3}$ steps to solve the 3SUM problem. That is, that 3SUM problem will be solved in $O(n^{3})$ time using brute force comparison.

We can however lower this upper bound using other algorithms. By sorting $A$ and $B$ using mergesort such that $$A = [a'_{1},a'_{2},\ldots, a'_{n}]$$ where $a'_{1}\le a'_{2}\le \ldots a'_{n}$ and similarly for $B$, we can make a doubly sorted array. $$MATRIX$$



PISIKA Copyright © 2009