Search code examples
time-complexitybig-o

What's the Time Complexity of two separate inner loops nested in an outer loop?

A student just asked me a question that I haven't considered before. What is the time complexity of an algorithm in which there are two inner loops for one outer loop:

l = [0,1,2,3,4,....]

for i in range (len(l)):
   
    for n in range(len(l):
        #inner loop 1 code

    for j in range(len(l):
        #inner loop 2 code

I have no specific algorithm in mind, it's just a hypothetical question.

My gut instinct was that it would still be O(n^2)... However I didn't have the necessary explanation or certainty of my position. Does the second inner loop affect the time complexity?

Solution

  • You are correct. For your trivial example, you can even calculate the exact number of loop steps that will be executed: n(n + n) = 2n2.

    Now, since big-O notation ignores constant coefficients, we have that O(2n2) = O(n2).

    If your two inner loops execute different work, however, then you instead consider the one with the largest complexity.