Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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++){  
  //code  
  for(j = i + 1; j < n; j++){  
     //code  
  }  
}  

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

1 Answer 1

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

 
discard

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.