3Sum 2 Different implementations complexity These are 2 implementations for the http://en.wikipedia.org/wiki/3SUM problem,
The first one is mine.
and in the second one I implemented Wiki's pseudo code.

Can someone please tell me if there is a difference between the two in complexity of runtime and memory space? 

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication2
{

    //the 3SUM problem asks if a given set of n integers, 
    //each with absolute value bounded by some polynomial in n, contains three elements that sum to zero
    public class ThreeSum
    {
        public ThreeSum()
        {
            List&lt;int&gt; array = new List&lt;int&gt; { 25, -10, -7, -3, 2, 4, 8, 10 };
            List&lt;int&gt; res = SolveThreeSum(array);
            res = SolveThreeSumWiki(array);
        }

        public List&lt;int&gt; SolveThreeSum(List&lt;int&gt; array)
        {
            for (int i = 0; i &lt; array.Count - 2; i++ )
            {
                for (int j = i + 1; j &lt; array.Count -1; j++)
                {
                    for (int k = i + 2; k &lt; array.Count ; k++)
                    {
                        if ((array[i] + array[j] + array[k]) == 0)
                        {
                            return new List&lt;int&gt; { array[i], array[j], array[k] };
                        }   
                    }                    
                }
            }
            return null;
        }

        public List&lt;int&gt; SolveThreeSumWiki(List&lt;int&gt; array)
        {
            array.Sort();
            for (int i = 0; i &lt; array.Count - 3; i++)
            {
                int a = array[0];
                int start = i + 1;
                int end = array.Count - 1;
                while (start &lt; end)
                {
                    int b = array[start];
                    int c = array[end];
                    if ((a + b + c) == 0)
                    {
                        return new List&lt;int&gt; { a, b, c };
                    }                    
                    else if (a+b+c &gt; 0)
                    {
                        end = end - 1;
                    }
                    else
                    {
                         start = start + 1;
                    }
                }
            }
            return null;
        }
    }
}
Your version

You have a bug in your three-loop implementation. This sort of bug creeps in when you use copy/paste to code without being diligent about checking what's useful. In your 'k' loop you have:


for (int k = i + 2; k &lt; array.Count ; k++)



But that should loop from j + 1 and not i + 1. You should have:

for (int k = j + 1; k &lt; array.Count ; k++)


This will significantly improve your performance for large lists.

The performance of this option will scale in terms of \$O(n^3)\$ which means each time you double the input data size, you will take 8 times longer to compute a result.

Wiki Version

The second method uses the wiki algorithm, which is also the base of the algorithm I would recommend....

The Sort will take \$O(n \log{n})\$ time. For largeish lists the log(n) can be effectively ignored....

What's interesting here, is that you loop to the array size still in the i loop. You can actually limit the outer loop to valeus less than or equal to 0.

At least one of the values has to be 0 or less in order for there to be a zero-sum.

Similarly, once you have a second number, chosen from values after i, you should then be able to do a binary-search for the third number.