Let's rotulam os loops A, B e C:

"java int soma = 0; // laço A for(int i = 1; i < n; i++) { // loop B for(int j = 1; j < i * i; j++) { if(j % i == 0) { // loop C for(int k = 0; k < j; k++) { soma++; } } } }

- Loop A itera O(*n*) vezes.
- Loop B itera O(*i*2) vezes **por iteração de A***. Para cada uma destas iterações:
    - `j % i == 0` é avaliado, o que demora O(1) tempo.
    - Em 1/*i* destas iterações, o loop C itera *j* vezes, realizando O(1) trabalho por iteração. Como *j* é O(*i*2) em média, e isto só é feito para as iterações de 1/*i* do laço B, o custo médio é O(*i*2 / *i*) = O(*i*).

Multiplicando tudo isto em conjunto, obtemos O(*n* × *i*2 × (1 + *i*)) = O(*n* × *i*3). Uma vez que *i* é em média O(*n*), isto é O(*n*4).

---

A parte complicada disto é dizer que a condição "se" é apenas verdadeira 1/*i* do tempo:

> Basicamente, por que é que o can't j % i vai até i * i em vez de i?

De facto, `j` vai até `j < i * i`, não apenas até `j < i`. Mas a condição `j % i == 0` é verdadeira se e só se `j` for um múltiplo de `i`.

Os múltiplos de `i` dentro do intervalo são `i`, `2*i`, `3*i`, ..., `(i-1) * i`. Existem `i - 1` destes, por isso o loop C é atingido `i - 1` vezes apesar do loop B iterating `i * i - 1` vezes.

• O primeiro laço consome n iterações.
• A segunda volta consome iterações n*n. Imagine o caso quando i=n, depois j=n*n.
• O terceiro laço consome n' iterações, porque só é executadoi' vezes, onde i' está limitado an' no pior dos casos.

Assim, a complexidade do código é O(n×n×n×n).

Espero que isto o ajude a compreender.

Todas as outras respostas estão correctas, quero apenas emendar o seguinte. Queria ver, se a redução das execuções do k-loop interno era suficiente para reduzir a complexidade real abaixo de 'O(n⁴).`Então escrevi o seguinte:

``java para (int n = 1; n < 363; ++n) { int soma = 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) { soma++; } } } }

long cubic = (longo) Math.pow(n, 3);
hipCúbico longo = (comprido) Math.pow(n, 4);
parente duplo = (duplo) (soma / (duplo) hipCúbico);
System.out.println("n = " + n + ": iterações = " + soma +
        ", n³ = " + cúbico + ", n⁴ = " + hipCúbico + ", rel = " + relativo);

}

Depois de executar isto, torna-se óbvio, que a complexidade é de facto `n⁴`. As últimas linhas de saída parecem-se com isto:

n = 356: iterações = 1989000035, n³ = 45118016, n⁴ = 16062013696, rel = 0,12383254507467704 n = 357: iterações = 2011495675, n³ = 45499293, n⁴ = 16243247601, rel = 0,12383580700180696 n = 358: iterações = 2034181597, n³ = 45882712, n⁴ = 16426010896, rel = 0,1238390505075183874 n = 359: iterações = 2057058871, n³ = 46268279, n⁴ = 16610312161, rel = 0,1238422764747628734 n = 360: iterações = 2080128570, n³ = 46656000, n⁴ = 16796160000, rel = 0,12384548432498857 n = 361: iterações = 2103391770, n³ = 47045881, n⁴ = 16983563041, rel = 0,12384867444612208 n = 362: iterações = 2126849550, n³ = 47437928, n⁴ = 17172529936, rel = 0,1238518469862343

O que isto mostra é que a diferença relativa real entre a `n⁴' real e a complexidade deste segmento de código é um factor assimptótico para um valor em torno de `0,124...` (na realidade 0,125). Embora não nos dê o valor exacto, podemos deduzir, o seguinte:

A complexidade temporal é `n⁴/8 ~ f(n)` onde `f` é a sua função/método.

* A página wikipedia na notação Big O declara nas tabelas de 'Notações da Família de Bachmann-Landau' que o `~` define o limite dos dois lados do operando é igual. Ou:
> f é igual a g assimptóticamente 

(Escolhi 363 como limite superior excluído, porque `n = 362` é o último valor para o qual obtemos um resultado sensato. Depois disso, excedemos o espaço longo e o valor relativo torna-se negativo).

O utilizador kaya3 descobriu o seguinte:
> A constante assimptótica é exactamente 1/8 = 0,125, a propósito; [aqui está a fórmula exacta via Wolfram Alpha][1].

  [1]: https://www.wolframalpha.com/input/?i=sum+for+i+%3D+1+to+n-1+of+i+*+i+*+%28i-1%29+%2F+2
***  ***

Deixemos's dar uma vista de olhos aos dois primeiros loops.

A primeira é simples, it's looping de 1 a n. A segunda é mais interessante. Passa de 1 para i ao quadrado. Vamos's ver alguns exemplos:

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  

No total, os loops i e j combinados têm1^2 + 2^2 + 3^2. Existe uma fórmula para a soma dos primeiros n quadrados,n (n+1) (2n + 1) / 6, que é aproximadamenteO(n^3)`.

Tem um último k loop que faz loops de 0 a j se e só se j % i == 0. Uma vez que j vai de 1 a i^2, j % i == 0 é verdadeiro para i vezes. Uma vez que o i loop itera sobre n, tem um O(n)adicional.

Então tem O(n^3) de i e j loops e outro O(n) de k loop para um total de O(n^4)

Remover if e modulo sem alterar a complexidade

Aqui está o 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;
}

Se estiver confuso com o "se" e o módulo, pode simplesmente refactorizê-los, com o "j" saltando directamente de "i" para "2i" para "3i"... ... :

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

Para facilitar ainda mais o cálculo da complexidade, pode introduzir uma variável intermediária j2, de modo a que cada variável de laço seja incrementada em 1 a cada iteração:

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;
}

Pode utilizar o System.out.println debugging ou old-school para verificar que i, j, k triplet é sempre o mesmo em cada método.

Expressão de formulário fechado

Como mencionado por outros, pode utilizar o facto de que a soma dos primeiros inteiros n é igual a n * (n+1) / 2 (ver números triangulares). Se utilizar esta simplificação para cada laço, obtém :

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

Obviamente não é a mesma complexidade que o código original, mas devolve os mesmos valores.

Se pesquisar no Google os primeiros termos, pode notar que 0 0 0 2 11 35 85 175 322 546 870 1320 1925 2717 3731 aparecem em "Stirling numbers of the first kind: s(n+2, n)", com dois 0s adicionados no início. Isto significa que o sum é o número Stirling do primeiro tipo s(n, n-2).