Hey there! Let's break this down step by step—you've already nailed the first two loops, so let's build on that to figure out the third layer, then cover the general approach for these kinds of problems.

First, Let's Calculate the Total Execution Count for Your Loops #

Your loops look like this (I'll write them in a code-like format for clarity):

for i from 1 to n:
    for j from i to n:
        for k from i to j+1:
            # Your code here

Step 1: Count the third loop's runs per outer iteration #

For a fixed i and j, the third loop runs from k=i to k=j+1. Assuming this is a closed-interval loop (includes both start and end values), the number of iterations is:
(j+1 - i + 1) = j - i + 2
(Quick check: if i=1, j=1, k runs 1→2, which is 2 iterations—1-1+2=2, correct.)

Step 2: Expand the total into a triple sum #

The total number of operations T(n) is the sum of the third loop's count across all valid i and j:

T(n) = Σ (i=1 to n) Σ (j=i to n) (j - i + 2)

Step 3: Simplify the sums with variable substitution #

Let's make this easier by substituting d = j - i (since j ≥ i, d starts at 0 and goes up to n-i). Then j = i + d, and the inner sum becomes:

Σ (d=0 to n-i) (d + 2) = Σ(d=0 to n-i) d + Σ(d=0 to n-i) 2

We can compute these standard sums:

• Σ(d=0 to m) d = m(m+1)/2 (here m = n-i)
• Σ(d=0 to m) 2 = 2*(m+1)

Combining these gives:

[(n-i)(n-i+1)/2] + 2*(n-i+1) = (n-i+1) * [(n-i)/2 + 2] = (n-i+1)(n-i+4)/2

Now substitute back into the outer sum, and let m = n - i + 1 (so when i=1, m=n; when i=n, m=1—the sum order doesn't matter):

T(n) = (1/2) Σ(m=1 to n) m(m+3) = (1/2) Σ(m=1 to n) (m² + 3m)

Step 4: Compute the final sum and find the dominant term #

Using standard summation formulas:

• Σ(m=1 to n) m² = n(n+1)(2n+1)/6
• Σ(m=1 to n) 3m = 3n(n+1)/2

Combine and simplify:

T(n) = (1/2) [ n(n+1)(2n+1)/6 + 3n(n+1)/2 ]
= (1/2)n(n+1) [ (2n+1)/6 + 9/6 ]
= (1/2)n(n+1)(2n+10)/6
= n(n+1)(n+5)/6

The dominant term here is n³/6, so the time complexity is O(n³).

General Approach for Dependent Loop Bounds #

Whenever you have nested loops where inner bounds depend on outer variables, follow these steps:

1. Write the iteration count for each inner loop as an expression using the outer loop variables.
2. Convert the total operations into a multiple summation (one sum per loop level).
3. Simplify the sums using variable substitutions or standard summation formulas (like sums of constants, linear terms, squares, etc.).
4. Identify the dominant term of the final sum—drop lower-order terms and constant coefficients to get the Big O complexity.

This method works for any number of nested loops, even if each layer's bounds depend on all previous ones.

内容的提问来源于stack exchange，提问作者Dazcii