Explanation of the complexity of a loop [duplicate]

This question already has an answer here:

I am confused on the following:
In the following trivial code:

for (int i = 0; i < n; i++) {
for(int j = i + 1; j < n; j++) {
for(int k = j + 1; k < n; k++) {
//some code here
}
}
}

I know that the complexity is N^3. But I am confused on some details.
The outer loop is executed N times.
The inner loop I thought that it was executed N*(N-1) times but when I tested with a small example of n=5 it is executed actually N*(N-1)/2 times. And the inner most loop I am lost on how the exact number of times it is executed. I originally thought that it is executed N(N-1)(N-2) but this is wrong again by using a small n the numbers don't work out.
So my question is:
1) Can someone help me understand how the exact complexity is calculated on this trivial example?
2) What is the usual process? Do we select some small numbers and try to derive a formula or what?

marked as duplicate by Raphael♦Jun 13 '14 at 23:00

You are right that the outer-loop is executed $N$ times, and you are almost right regarding the inner loop. Observe that the inner-loop does not loop the same amount of times at every iteration of the outer-loop. In particular, it will first loop $N-1$ times when $i = 0$, then it will loop $N-2$ times when $i = 1$, $N-3$ times when $i = 2$, and so forth. Therefore, the inner-loop is executed $(N-1) + (N-2) + \ldots + 1 + 0$ times which is the following well known summation: $$\sum_{i=0}^{N-1}i = \frac{(N-1)\cdot N}{2}$$
In general, you will model the loops as summations, and simply evaluate the sum. In your example, you will have that: $$T(N) = \sum_{i = 0}^{N-1}{\sum_{j = i+1}^{N-1}\sum_{k=j+1}^{N-1}}O(1)$$ and evaluating this will give you your $O(N^3)$ answer. Remember that the goal is to "count" the number of primitive operations by the algorithm in question.
• Again, you are quite close. If you evaluate the summations given for $T(N)$, you will get that $T(N) = \frac{(N-2)(N-1)N}{6}$. – user340082710 Jun 14 '14 at 16:50