Follow

Keep Up to Date with the Most Important News

By pressing the Subscribe button, you confirm that you have read and are agreeing to our Privacy Policy and Terms of Use
Contact

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

>Solution :

MEDevel.com: Open-source for Healthcare and Education

Collecting and validating open-source software for healthcare, education, enterprise, development, medical imaging, medical records, and digital pathology.

Visit Medevel

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

Add a comment

Leave a Reply

Keep Up to Date with the Most Important News

By pressing the Subscribe button, you confirm that you have read and are agreeing to our Privacy Policy and Terms of Use

Discover more from Dev solutions

Subscribe now to keep reading and get access to the full archive.

Continue reading