1

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?

4

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.

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.