CODEWITHSUNDEEP
pythoncomplexity-theorypythagorean
trap28
trap28

Reputation: 97

What is the complexity of this pythagorean triplet function?

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)?

Upvotes: 1

Views: 107

Answers (1)

Rob Bricheno
Rob Bricheno

Reputation: 4653

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

Upvotes: 2

Related Questions