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 haven't touched algorithm complexity stuff in quite a while, so I am trying to do a refresher.

I am trying to figure out the number of steps in the following for loop.

for(i = 0; i < n; i++){  
  for(j = i + 1; j < n; j++){  

The inner loop will be executed enter image description here times
I mean t times for each value of j. Right?

In the worst case tj will be equal to n-i. Since it will run for n-(i+1)-1 times.

Well is my approach on this analysis correct?

share|improve this question
up vote 4 down vote accepted

The inner code will be executed (n-1)*(n/2) times.

Looking at the first few iterations and the end conditions helps give a general pattern

When i=0, the inner code will go from 1 to n - (n-1 times)
When i=1, the inner code will go from 2 to n - (n-2 times)
When i=n-2, the inner code will go from (n-1) to n - (n-(n-1))

So (n-1) + (n-2) + ... + (n-(n-1)) = (n-1)*(n/2)

share|improve this answer
Yes this makes sense to me.I was trying to figure out if Tj had a steady worse case time across all loops – user10326 Oct 22 '11 at 19:49
:BTW isn't it (n(n-1))/2? – user10326 Oct 25 '11 at 15:44
@user10326, You are correct, I did say approximately in the original answer but I've edited it to be more precise – jhulst Oct 25 '11 at 20:12

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.