Attualmente sto leggendo la sezione Analisi degli algoritmi in Algorithms, 4a edizione e sto cercando di capire come l'autore ha calcolato (N ^ 2) / 2 e (N ^ 3) / 6 frequenze di esecuzione nello snippet di codice seguente ( qui è il codice completo):
public class ThreeSum
{
public static int count(int[] a) {
int N = a.length;
int cnt = 0;
for (int i = 0; i < N; i++) { // <---------------- 1
for (int j = i+1; j < N; j++) { // <---------- N
for (int k = j+1; k < N; k++) { // <------ N^2/2
if (a[i] + a[j] + a[k] == 0) { // <--- N^3/6
cnt++; // <---------------------- x
}
}
}
}
return cnt;
}
}
Perché dividere N ^ 2 per 2? Perché dividere N ^ 3 per 6?