Algorithm analysis refresher help

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 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?

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)

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