Vamos a etiquetar los bucles A, B y C:

int suma = 0;
// bucle A
for(int i = 1; i < n; i++) {
    // bucle B
    for(int j = 1; j < i * i; j++) {
        if(j % i == 0) {
            // bucle C
            for(int k = 0; k < j; k++) {
                suma++;
            }
        }
    }
}

• El bucle A itera O(n) veces.
• El bucle B itera O(i2) veces por iteración de A. Para cada una de estas iteraciones
  • j % i == 0 se evalúa, lo que lleva O(1) tiempo.
  • En 1/i de estas iteraciones, el bucle C itera j veces, haciendo O(1) trabajo por iteración. Como j es O(i2) en promedio, y esto sólo se hace para 1/i iteraciones del bucle B, el coste medio es O(i2 / i) = O(i).

Multiplicando todo esto, obtenemos O(n × i2 × (1 + i)) = O(n × i3). Como i es en promedio O(n), esto es O(n4).

La parte complicada de esto es decir que la condición "si" sólo se cumple 1/i de las veces:

Básicamente, ¿por qué j % i no puede llegar a i * i en lugar de i?

De hecho, j llega hasta j < i * i, no sólo hasta j < i. Pero la condición j % i == 0 es verdadera si y sólo si j es un múltiplo de i.

Los múltiplos de i dentro del rango son i, 2*i, 3*i, ..., (i-1) * i. Hay i - 1 de estos, por lo que el bucle C se alcanza i - 1 veces a pesar de que el bucle B itera i * i - 1 veces.

• El primer bucle consume "n" iteraciones.
• El segundo bucle consume n*n iteraciones. Imagina el caso en que i=n, entonces j=n*n.
• El tercer bucle consume n iteraciones porque se ejecuta sólo i veces, donde i está limitado a n en el peor caso.

Así, la complejidad del código es O(n×n×n×n).

Espero que esto te ayude a entenderlo.

Todas las demás respuestas son correctas, sólo quiero corregir lo siguiente. Quería ver, si la reducción de las ejecuciones del k-loop interno era suficiente para reducir la complejidad real por debajo de O(n⁴). Así que escribí lo siguiente:

para (int n = 1; n < 363; ++n) {
    int sum = 0;
    for(int i = 1; i < n; ++i) {
        para(int j = 1; j < i * i; ++j) {
            si(j % i == 0) {
                para(int k = 0; k < j; ++k) {
                    suma++;
                }
            }
        }
    }

    largo cúbico = (largo) Math.pow(n, 3);
    largo hipCúbico = (largo) Math.pow(n, 4);
    doble relativo = (doble) (suma / (doble) hipCúbico);
    System.out.println("n = " + n + ": iteraciones = " + suma +
            ", n³ = " + cúbico + ", n⁴ = " + hipCúbico + ", rel = " + relativo);
}

Después de ejecutar esto, se hace evidente, que la complejidad es de hecho "n⁴". Las últimas líneas de salida se ven así:

n = 356: iteraciones = 1989000035, n³ = 45118016, n⁴ = 16062013696, rel = 0.12383254507467704
n = 357: iteraciones = 2011495675, n³ = 45499293, n⁴ = 16243247601, rel = 0.12383580700180696
n = 358: iteraciones = 2034181597, n³ = 45882712, n⁴ = 16426010896, rel = 0.12383905075183874
n = 359: iteraciones = 2057058871, n³ = 46268279, n⁴ = 16610312161, rel = 0.12384227647628734
n = 360: iteraciones = 2080128570, n³ = 46656000, n⁴ = 16796160000, rel = 0.12384548432498857
n = 361: iteraciones = 2103391770, n³ = 47045881, n⁴ = 16983563041, rel = 0.12384867444612208
n = 362: iteraciones = 2126849550, n³ = 47437928, n⁴ = 17172529936, rel = 0.1238518469862343

Lo que esto muestra es que la diferencia relativa real entre el "n⁴" real y la complejidad de este segmento de código es un factor asintótico hacia un valor alrededor de "0.124..." (en realidad 0.125). Aunque no nos da el valor exacto, podemos deducir, lo siguiente:

La complejidad temporal es "n⁴/8 ~ f(n)` donde "f" es su función/método.

• La página de Wikipedia sobre la notación Big O afirma en las tablas de la "Familia de notaciones de Bachmann-Landau" que el límite de los dos lados de la operando es igual. O:

  f es igual a g asintóticamente

(Elegí 363 como límite superior excluido, porque n = 362 es el último valor para el que obtenemos un resultado sensato. Después de eso, excedemos el espacio largo y el valor relativo se vuelve negativo).

El usuario kaya3 averiguó lo siguiente:

La constante asintótica es exactamente 1/8 = 0.125, por cierto; aquí está la fórmula exacta a través de Wolfram Alpha.

Veamos los dos primeros bucles.

El primero es sencillo, va de 1 a n. El segundo es más interesante. Va de 1 a i al cuadrado. Veamos algunos ejemplos:

e.g. n = 4    
i = 1  
j loops from 1 to 1^2  
i = 2  
j loops from 1 to 2^2  
i = 3  
j loops from 1 to 3^2  

En total, los bucles i y j combinados tienen 1^2 + 2^2 + 3^2.
Hay una fórmula para la suma de los primeros n cuadrados, n * (n+1) * (2n + 1) / 6, que es aproximadamente O(n^3).

Tienes un último "bucle k" que va de 0 a "j" si y sólo si "j % i == 0". Como j va de 1 a i^2, j % i == 0 es cierto para i veces. Como el bucle i itera sobre n, tienes un O(n) extra.

Así que tienes O(n^3) de los bucles i y j y otro O(n) del bucle k para un total de O(n^4).

Quitar "si" y "modulo" sin cambiar la complejidad

Aquí está el método original:

public static long f(int n) {
    int sum = 0;
    for (int i = 1; i < n; i++) {
        for (int j = 1; j < i * i; j++) {
            if (j % i == 0) {
                for (int k = 0; k < j; k++) {
                    sum++;
                }
            }
        }
    }
    return sum;
}

Si estás confundido por el "si" y el "módulo", puedes refactorizarlos, con "j" saltando directamente de "i" a "2i" a "3i"... :

Para facilitar aún más el cálculo de la complejidad, puedes introducir una variable intermedia "j2", de modo que cada variable del bucle se incremente en 1 en cada iteración:

public static long f3(int n) {
    int sum = 0;
    for (int i = 1; i < n; i++) {
        for (int j2 = 1; j2 < i; j2++) {
            int j = j2 * i;
            for (int k = 0; k < j; k++) {
                sum++;
            }
        }
    }
    return sum;
}

Puedes usar la depuración o la vieja escuela System.out.println para comprobar que i, j, k triplete es siempre el mismo en cada método.

Expresión de forma cerrada

Como ya se ha mencionado, se puede utilizar el hecho de que la suma de los primeros n números enteros es igual a n * (n+1) / 2 (ver números triangulares). Si usas esta simplificación para cada bucle, obtienes :

public static long f4(int n) {
    return (n - 1) * n * (n - 2) * (3 * n - 1) / 24;
}

Obviamente no es la misma complejidad que el código original, pero devuelve los mismos valores.

Si buscas en Google los primeros términos, puedes notar que 0 0 0 2 11 35 85 175 322 546 870 1320 1925 2717 3731 aparecen en "Números de Stirling de la primera clase: s(n+2, n).", con dos 0s añadidos al principio. Significa que "suma" es el número de Stirling de la primera clase s(n, n-2).