What is the complexity of this pythagorean triplet function?

Question

def tuplePyth(n):
    list_=[]
    for x in range(1, n):
        for y in range(x + 1, (n - x) // 2):
            for z in range (y + 1, n - x - y):
               if smallestTrip(x, y, z)==False:
                    list_.append([x,y,z])
    print (list_)

def pythTrue(a,b,c):
    (A,B,C) = (a*a,b*b,c*c)
    if A + B == C or B + C == A or A + C == B:
        return True

def smallestTrip(a,b,c):
    if pythTrue(a,b,c) == True:
        if (a+b+c)%12 == 0:
            return True
        else:
            return False

smallestTrip checks if x,y,z are multiples of the basic 3,4,5 right triangle.

The goal is to generate all possible pythagorean triplets the sum of which is less than an inputed sum, n.

(these triplets must NOT be multiples of the (3,4,5) triangle.)

Is the complexity here O(nnlogn)?

score 2 · Accepted Answer · answered Nov 04 '18 at 15:42

2

The other functions are O(1) and you have three loops with respect to n in the original problem. So the complexity is O(n * n * n) = O(n^3)

This question may provide further illumination Time complexity of nested for-loop

answered Nov 04 '18 at 15:42

Rob Bricheno

4,467
15
29

What is the complexity of this pythagorean triplet function?

1 Answers1