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

Question

Can someone explain why this algorithm O(n^2)? According to this , this is O (n ^ 2). The reason I think O (n ^ 3) is because the outer loop (for x) runs nonce, the inner loop (for y) runs n-1once, and in the script the worst one, for example A = [8, 100, 101, 102, 103, 104, 105, 106, 107], while ((for z) will be run n-2once, in general O(n^3).

For completeness A, a sorted array with positive elements, the 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

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;
}

for A.lenght - (x+1) , .. O(n). while A.length - (x+2) , z, A.length - (x+2) , while. , O(n). , O(n) + O(n) = O(n).

O(n) x, O(n^2).

KMP .

Answer 2

, z x-loop, y-loop. x- z A.length - x - 2 .

Answer 3

, z in total A.Length: . :

• x = 0, y = 1, z, 2 A. , y- z .

Answer 4

.

, , n . , " -", n . , 3 O (n).

, , :

The variable z is declared inside the x-loop, not the y-loop, so z will not be reinitialized every time the y-loop is completed. This means that z will increase to A.length only once in each pass of the x-cycle. Once z reaches A.length, it will no longer increase and therefore will not depend on the y-cycle. I hope that this explanation will be adequate and that this problem will become clearer for you now.