TapeEquilibrium implementation I took a test at Codility called TapeEquilibrium. The task description that I received can be seen here.

I came up with a solution that worked, and I was pretty happy with. However, the performance was apparently awful. The expected time complexity is apparently supposed to be \$O(N)\$, but I got \$O(N * N)\$. I'm not quite sure what exactly that means, but I've heard about it several times.

I'd like some help on improving my solution and get information about what I did wrong and how it could be done better, and why. I'm doing this to learn and improve.

public int solution(int[] A) {
    int min = Int32.MaxValue;
    for (int i = 0; i &lt; A.Length - 1; i++) {
        // p = i + 1            
        int part1 = 0, part2 = 0;
        for (int j = 0; j &lt;= i; j++) part1 += A[j];
        for (int j = i + 1; j &lt;= A.Length - 1; j++) part2 += A[j];

        int val = Math.Abs(part1 - part2);
        if (val &lt; min) min = val;
    }
    return min;
}
Style  

Initializing of multiple variables on one line removes readability.
Writing for loops on one line removes readability.  

Dead code should be deleted (// p = i + 1)  

Bug  

It seems that you have a little unnoticed bug in your code. Your loop  


for (int i = 0; i &lt; A.Length - 1; i++) {  



misses the last element of your array.


Problem  

Let us assume we have an array A containing 8 elements like  

3 5 7 2 5 2 1 3

The ideal divider would be if the arrays left half summed up would be equal to the right half summed up.
Unfortunatetly here  

sumLeft = A[0] + A[1] + A[2] + A[3] == 17
sumRight = A[4] + A[5] + A[6] + A[7] == 11
difference = sumLeft - sumRight == 6   

So as we see that the left half &gt; right half let us take the last element of the left side and check if 2 * A[half-1] &lt;= difference wich is 2 * 2 &lt;= 6 so we can do 

sumLeft = sumLeft - A[3] == 15
sumRight = sumRight + A[3] == 13
difference = difference - 2 * A[3] == 2  

Or simplified for sumLeft &gt; sumRight  

difference = sumLeft - sumRight;
while (2*A[currentHalf-1] &lt;= difference)
{
    currentHalf = currentHalf -1;
    sumLeft = sumLeft - A[currentHalf]
    sumRight = sumRight + A[currentHalf]
    difference = difference - 2 * A[currentHalf];
}


EDIT : Based on @Dmitry's comments I rechecked the algorithm and came to the result that this algorithm only works for positive numbers.

And my implementation of the above  

public int solution(int[] A)
{
    int length = A.Length;
    int sumLeft = 0;
    int sumRight = 0;

    int currentArrayHalf = length / 2;

    for (int i = 0; i &lt; currentArrayHalf; i++)
    {
        sumLeft = sumLeft + A[i];
        sumRight = sumRight + A[i + currentArrayHalf];
    }

    Boolean isEven = length % 2 == 0;

    if (!isEven) { sumRight = sumRight + A[length - 1]; }

    int step = 1;
    if (sumLeft &gt; sumRight)
    {
        step = -1;
        if (isEven)
        {
            currentArrayHalf--;
        }
    }

    int difference = Math.Abs(sumLeft - sumRight);
    if (difference == 0) { return difference; }

    while (currentArrayHalf &gt;= 0 &amp;&amp; currentArrayHalf &lt; length &amp;&amp; 2 * A[currentArrayHalf] &lt;= difference)
    {
        sumLeft = sumLeft - A[currentArrayHalf];
        sumRight = sumRight + A[currentArrayHalf];
        difference = difference - 2 * A[currentArrayHalf];
        currentArrayHalf = currentArrayHalf + step;
    }

    return difference;
}