How to Analyze Time Complexity of Nested Loops and Sequences

Simple Loop Analysis (O(n))

Basic Incrementing Loop

for i in range(n):  # i from 0 to n-1
    statement

The loop runs n times.
The statement executes exactly n times.
Time complexity: O(n).

Decrementing Loop

i = n
while i > 0:
    statement
    i -= 1

Goes from n down to 1 → still n steps.
Whether you go up (1 to 10) or down (10 to 1), the number of iterations is the same.
Time complexity: O(n).

Loop with Step Size (c)

for i in range(1, n, 2):  # step size 2
    statement

If incrementing by 2, loop runs about n/2 times → still O(n).
If incrementing by 20, it runs about n/20 times → still O(n).
Key rule: A constant divisor or multiplier does not change the polynomial degree; complexity remains O(n).

Nested Loops (O(n²))

Standard Nested Loop (i and j both range over n)

for i in range(n):
    for j in range(n):
        statement

Inner loop runs n times for each of the n outer iterations.
Total executions = n · n = n².
Time complexity: O(n²).

Nested Loop with j Dependent on i

for i in range(n):        # i from 0 to n-1
    for j in range(0, i): # j from 0 to i-1
        statement

Tracing the execution:

When i = 0: j runs 0 times.
When i = 1: j runs 1 time.
When i = 2: j runs 2 times.
...
When i = n-1: j runs n-1 times.

Total iterations: 0 + 1 + 2 + ... + (n-1) = n(n-1)/2

The highest degree term is n²/2, so:

Time complexity: O(n²).
Note: Even though the inner loop runs fewer times on average, the degree of the polynomial is still n².

Loop with Changing Variable (O(√n))

p = 0
for i in range(1, n):
    if p <= n:
        p += i
    else:
        break

Here, p accumulates the sum of the first k integers: 1 + 2 + ... + k = k(k+1)/2.
The loop stops when p > n.
Condition: k(k+1)/2 > n.
Approximate: k² > n, so k ≈ √n.
Time complexity: O(√n).

Example:

If n = 100, p becomes 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 66, 78, 91, 105 → stops at 105 > 100, running about 14 times ≈ √100 = 10. The actual number is close to √n.
This shows that not all loops run n times; you must trace the variable's growth.

Key Takeaways

| Loop Type | Example | Number of Iterations | Complexity | |---|---|---|---| | Simple increment | for i in range(n) | n | O(n) | | Decrement | i = n; while i > 0: i-- | n | O(n) | | Step constant | for i in range(0, n, k) | n/k | O(n) | | Standard nested | for i in range(n)... for j in range(n) | n² | O(n²) | | Dependent inner | for i in range(n)... for j in range(i) | n(n-1)/2 | O(n²) | | Accumulating p | p += i until p > n | ≈ √n | O(√n) |

Always analyze the growth of the variable controlling the loop, not just a quick glance, especially when the increment or condition is non-standard. For a deeper understanding of how these patterns translate to formal notation, see the section on Understanding Time and Space Complexity: A Comprehensive Guide to Big O Notation and additional methods like the Algorithm Complexity: Frequency Count Method for Time Space Analysis. To strengthen your foundational comprehension, check out Time & Space Complexity Basics: Big O Notation Explained for DSA and How to Write and Analyze Algorithms: Time and Space Criteria.

How to Analyze Time Complexity of Nested Loops and Sequences

Simple Loop Analysis (O(n))

Basic Incrementing Loop

Decrementing Loop

Loop with Step Size (c)

Nested Loops (O(n²))

Standard Nested Loop (i and j both range over n)

Nested Loop with j Dependent on i

Loop with Changing Variable (O(√n))

Key Takeaways

Related summaries

Time Complexity Analysis of Loop Variations in Code

Understanding Time and Space Complexity: A Comprehensive Guide to Big O Notation

Asymptotic Analysis Part 3: Growth Rates & Time Complexity

Time & Space Complexity Basics: Big O Notation Explained for DSA

Algorithm Complexity: Frequency Count Method for Time Space Analysis

Most viewed summaries

A Comprehensive Guide to Using Stable Diffusion Forge UI

Kolonyalismo at Imperyalismo: Ang Kasaysayan ng Pagsakop sa Pilipinas

Mastering Inpainting with Stable Diffusion: Fix Mistakes and Enhance Your Images

Pamamaraan at Patakarang Kolonyal ng mga Espanyol sa Pilipinas

How to Install and Configure Forge: A New Stable Diffusion Web UI

Start taking better notes today with LunaNotes