Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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


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.