Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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?

share|improve this question

1 Answer 1

up vote 4 down vote accepted

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.

share|improve this answer
    
+1 Thanks for the very helpful link and explanation! –  Anthony Aug 16 '12 at 22:18

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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