1

Time complexity of nested loop dependent on the outer loop

This is a normal nested loop with n^2 complexity

for i in range(n):
    for j in range(n): # <-- dependent on n
        print(i,j)

I am having a hard time understanding why the next loop also has a n^2 complexity even when it prints less statements

for i in range(n):
   for j in range(i): # <-- now it is dependent on i
       print(i,j)

any ideas?

Submitted May 24th 2021 by Admin

Answers
0

Let's count the amount of times the innermost expression executes, so we put it this way:

  • i = 0; j = 0; innermost executes: 0 times
  • i = 1; j = 0, 1; innermost executes: 1 time
  • i = 2; j = 0, 1, 2; innermost executes: 2 times
  • i = 3; j = 0, 1, 2, 3; innermost executes: 3 times
  • ...

Thus, we'll have 1+2+3+...+n. Which is 1/2(n*(n+1)), which is n^2. Thus, the time complexity is still n^2.

Admin | 3 months ago



Relevant Questions