Why is this caterpillar algorithm O(n^2) not O(n^3)?

Question

Can someone explain why this algorithm is O(n^2)? According to this, it's O(n^2). The reason why I think it's O(n^3) is because outer loop (for x) runs n times, inner loop (for y) runs n-1 times, and in the worst scenario e.g. A = [8, 100, 101, 102, 103, 104, 105, 106, 107], the while loop (for z) will run n-2 times hence overall O(n^3).

For completeness, A is a sorted array with positive elements, a triplet (x, y, z) is a triangle if A[x] + A[y] > A[z]. Find how many triangles can be built from A.

        int TrianglesCount(int[] A)
        {
            int result = 0;
            for (int x = 0; x < A.Length; x++)
            {
                int z = x + 2;
                for (int y = x + 1; y < A.Length; y++)
                {
                    while (z < A.Length && A[x] + A[y] > A[z])
                        z++;
                    result += z - y - 1;
                }
            }
            return result;
        }

Answer 1

Let's take a closer look at the below snippet

int z = x + 2;
for (int y = x + 1; y < A.Length; y++)
{
   while (z < A.Length && A[x] + A[y] > A[z])
      z++;
   result += z - y - 1;
}

The for loop is clearly executed A.lenght - (x+1) times, which is O(n). However, the inner while loop is executed at most A.length - (x+2) times in total, because each such execution increments value of z, and it can be incremented at most A.length - (x+2) times until the while condition fails. Again, this is at most O(n). Thus, the total time complexity of this snippet can be bounded by O(n) + O(n) = O(n).

Since the snippet is run for every of O(n) values of x, the overall time complexity is O(n^2).

A similar idea is used in KMP algorithm for string matching.

Answer 2

You should note that z is initialized inside x-loop, not y-loop. And on every x-iteration z could be incremented maximum A.length - x - 2 times.