I am currently reading the Analysis of Algorithms section in Algorithms, 4th Edition and I’m trying to understand how the author calculated (N^2)/2 and (N^3)/6 frequencies of execution in the code snippet below (here is the full code):
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;
}
}
Why divide N^2 by 2? Why divide N^3 by 6?
It’s a part of using “partial sums” to determine the frequencies of execution. The specific section is “Useful Shortcuts” where it shows what eventuality exists for a given starting term order in a sequence.
0