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
>Solution :
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).