計算量O(N^2)に減らすには？

配列Aのなかから、成立する三角形の個数をカウントする問題
で、O(N**2)にするアルゴリズム、以下のほぼ同じ2つのコードで計算量が変わるのはなぜでしょうか？

下の場合、Aの配列が大きいとタイムオーバーになります。

def solution(A):#これだと通る
    # write your code in Python 3.6
  
    N = len(A)
    count = 0
    A.sort()
    for x in range(N):
        z = x + 2
        for y in range(x + 1, N):
            while z < N  and A[x] + A[y] > A[z]:
                z += 1    
            count += z - y - 1

    return count

# Testcase
A = [10, 2, 5, 1, 8, 12]
print(solution(A))

python
1def solution(A):#これだと通らない
2    # write your code in Python 3.6
3
4    N = len(A)
5    count = 0
6    A.sort()
7    print(A)
8    for x in range(N):
9        #z = x + 2
10        for y in range(x + 1, N):
11            z=y+1
12            print("x,y,z=",x,y,z)
13            cnt=0
14            while z < N  and A[x] + A[y] > A[z]:
15                cnt+=1
16                print("z=",z)
17                z += 1
18            count += cnt
19            
20    print("ans=",count)
21    return count
22# Testcase
23A = [10, 2, 5, 1, 8, 12]
24print(solution(A))