1

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?

1 Answer 1

4

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)

3
  • Yes this makes sense to me.I was trying to figure out if Tj had a steady worse case time across all loops
    – user10326
    Commented Oct 22, 2011 at 19:49
  • :BTW isn't it (n(n-1))/2?
    – user10326
    Commented Oct 25, 2011 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
    Commented Oct 25, 2011 at 20:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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