# Time complexity of a triple nested for loop for ThreeSum problem [duplicate]

This question already has an answer here:

I am new to Algorithms and am currently confused about the running time of the ThreeSum program. If we look at ThreeSum's count function:

public static int count(int[] a) {
int N     = a.length;
int count = 0;

for (int i = 0; i < N; i++) <-- A
for (int j = i + 1; j < N; j++) <-- B
for (int k = j + 1; k < N; k++) <-- C
// check each triple
if (a[i] + a[j] + a[k] == 0)
count++;
// loop i = 0; j = i+1; k = j+1 so that we get each triple just once

return count;
}

I understand that int N = a.length means that its frequency is 1 as the statement only runs once and that count++'s frequency is x as it depends on input however with nested for loops. I understand that say A's frequency is $N$ (as it is repeated N times) but then I get a bit confused.

It seems to be that for each nested loop, the other loop has to run which makes sense so B's frequency is $N^2$ but then in the book it says that B's frequency is $N^2/2$ and C is $N^3/6$ (where I would have assumed $N^2$ and $N^3$) where is the "$/2$" and "$/6$" coming from?

Any help is appreciated, thanks. Sorry for the lengthy question!

## marked as duplicate by Raphael♦Sep 2 '13 at 10:29

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

• If you think this question differes significantly from the linked one, feel free to flag or vote for reopening. – Raphael Sep 2 '13 at 10:30

## 1 Answer

The second loop runs only on $j > i$. Only (roughly) half of the pairs $(i,j)$ between $0$ and $N-1$ satisfy $j > i$. Similarly, the third loop runs only on $k > j > i$, and only (roughly) $1/3!$ of the triples $(i,j,k)$ satisfy that condition.

If you want to be more accurate, $B$ runs this many times $$\sum_{i=0}^{N-1} (N-i-1) = \sum_{i=0}^{N-1} i = \frac{i(i-1)}{2}.$$ I'll leave you the calculation for $C$.