Hey there! Let's break down these two algorithms and figure out what's going on with their time complexity, since your initial O(n⁵) guess doesn't quite match the runtime behavior you're seeing (but there's a good reason for that!).

First, Let's Look at the Two Algorithms #

Algorithm 1 #

sum = 0;
for( i=1; i<n; i++ )
    for( j=0; j<i*n; j++ )
        for( k=0; k<j; k++)
            sum++;

Algorithm 2 #

sum = 0;
for( i=1; i<n; i++ )
    for( j=1; j<i*n; j++ )
        if( j%1 == 0 )
            for( k=0; k<j; k++ )
                sum++;

A Quick Note on Algorithm 2 #

First off, that if(j%1 == 0) check is a red herring—every integer modulo 1 is 0, so this condition is always true. That means Algorithm 2 behaves exactly like Algorithm 1, which is why their runtimes are nearly identical. No surprises there!

Calculating the Time Complexity #

Let's walk through the math step by step, focusing on asymptotic behavior (how the runtime grows as n gets very large—constants and small terms don't matter for big-O notation).

1. Outer Loop: i runs from 1 to n-1. For large n, this is roughly n iterations.

2. Middle Loop: For each i, j runs from 0 to i*n - 1 (or 1 to i*n -1 in Algorithm 2—again, the +1/-1 doesn't matter for large n). That's i*n iterations per outer loop step.

3. Inner Loop: For each j, k runs from 0 to j-1, which is j iterations. To find the total inner loop operations per outer loop step, we sum j from 0 to i*n -1:
   $$\sum_{j=0}^{i n -1} j = \frac{(i n -1) \cdot i n}{2} \approx \frac{i^2 n^2}{2}$$
   We can ignore the -1 here because it's negligible compared to i*n when n is large.

4. Total Operations: Now we sum that value over all i from 1 to n-1:
   $$\sum_{i=1}^{n-1} \frac{i^2 n^2}{2} = \frac{n^2}{2} \sum_{i=1}^{n-1} i^2$$
   The sum of squares formula $\sum_{i=1}^k i^2 = \frac{k(k+1)(2k+1)}{6}$ simplifies to roughly $\frac{n^3}{3}$ when k = n-1 (we only care about the highest-order term).

5. Final Asymptotic Result: Plugging that back in, we get:
   $$\frac{n^2}{2} \cdot \frac{n^3}{3} = \frac{n^5}{6}$$

   Since big-O notation ignores constant factors, this means the time complexity is O(n⁵).

Why Your Runtime Observations Make Sense #

• Difference from "pure" O(n⁵) algorithms: If you're comparing to a 5-level nested loop where each level runs exactly n times (e.g., for (a=0;a<n;a++) for (b=0;b<n;b++) ...), that algorithm does exactly n⁵ operations. Your algorithms only do ~n⁵/6 operations—so they're about 6x faster! But big-O doesn't care about constants, so both are still O(n⁵).
• Clear difference from O(n⁴) algorithms: When n gets large, n⁵ grows way faster than n⁴. For example, if n=100, n⁵ is 100x larger than n⁴. That's why you see a huge runtime gap between these algorithms and any O(n⁴) implementation.

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