CODEWITHSUNDEEP
pythontime-complexitybig-o
tryingtodobetter
tryingtodobetter

Reputation: 1

Big O time complexity for nested for loop (3 loop)

def unordered pair(arrayA, arrayB):
    for i in range(len(arrayA)):
        for j in range(len(arrayB)):
           for k in range(0, 100000):
               print(arrayA[i] + arrayB[j])

I just started Big O and need help on this example. If I tried to get the time complexity for each line, I know the first loop (for i loop) + the second loop (for j loop) equals O(ab). However, what is the time complexity for the last loop? (for k loop). I thought it should be O(n) since its just a simple for loop from 0 to n, but it turns out to be O(1)? Why is that? Thank you

Upvotes: 0

Views: 491

Answers (2)

Wumbo
Wumbo

Reputation: 90

Since the range for loop k is 0-100000 the time it will take will be constant.Hence O(1). I think the term is amortized time?

Upvotes: 0

Tim Biegeleisen
Tim Biegeleisen

Reputation: 522741

Appreciate that the third loop in k is actually fixed number of iterations, 100000 to be exact. This means that this third inner loop really just is a multiplier to the complexity of the outer two loops, and therefore won't affect the overall complexity by more than a constant.

The complexity of the two outer loops is just O(N*M), where N is the size of arrayA and M is the size of arrayB. Therefore, the overall complexity of the three nested loops is O(100,000 * N * M) which is just O(N*M).

Upvotes: 1

Related Questions