CODEWITHSUNDEEP
pythonbig-oanalysis
DonJon
DonJon

Reputation: 1

Big O of Four Double-Nested for loops

I'm trying to figure out what the Big O notation of this is. I know that the if this = n and that = m, the big O is O(mn), but if I have 4 in a row like this and worst case scenario it would run through all of them what would that do to my Big O notation.

def get_winner(self):      
    for this in range(self._this):
        for that in range(self._that - 2):
            # If statement here
                return

    for that in range(self._that):
        for this in range(self._this - 2):
            # If statement here
                return

    for this in range(self._this - 2):
        for that in range(self._that - 2):
            # If statement here
                return

    for this in range(self._this - 2):
        for that in range(self._that - 2):
            # If statement here
                return

Upvotes: 0

Views: 524

Answers (2)

zTizzle
zTizzle

Reputation: 31

You just add the 4 for loops that aren't nested in each other, so worst case would be 4 * (n * m), which is O(4nm) = O(nm)

Upvotes: 3

Naetmul
Naetmul

Reputation: 15592

It will be O(4mn), but since for any constant a, O(anm) = O(nm), so it will be O(mn) eventually.

Upvotes: 1

Related Questions