# 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 – 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