# 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

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

Relevant Questions

#### How to remove one element from list while iterate

September 19th 2021

#### Python Object Changing For No Apparent Reason

September 19th 2021

#### Multipy character position by ord() value of that character

September 16th 2021

#### I want to add a phrase "the Great" before every name in list names, why this did not work?

September 14th 2021

#### Filter function in Python (simple question)

September 13th 2021