1
$\begingroup$

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?

$\endgroup$

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

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.

2
$\begingroup$

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

A similar argument can be made to show what the runtime of the inner-most-loop is. In particular, you will get a similar type of summation.

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.

$\endgroup$
  • $\begingroup$ Very clear answer thank you. How can I brush up on the most fundamental summation formulation I must know for algorithm analysis? $\endgroup$ – Jim Jun 14 '14 at 10:20
  • $\begingroup$ I mean I am not sure what are the most fundamental summations to know. $\endgroup$ – Jim Jun 14 '14 at 10:23
  • $\begingroup$ Also I am not seem to be able to derive the inner most loop directly. I get N(N-1)(N-2)/2 which is wrong $\endgroup$ – Jim Jun 14 '14 at 12:22
  • $\begingroup$ 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}$. $\endgroup$ – user340082710 Jun 14 '14 at 16:50
  • $\begingroup$ What we give to our students learning this for the first time is the following cheat sheet: tug.org/texshowcase/cheat.pdf - There is a lot of extra stuff, but the bulk of pages 1 and 2 are quite useful! $\endgroup$ – user340082710 Jun 14 '14 at 16:51

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