Algorithm analysis refresher help

Question

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?

Answer 1

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)

• user10326: Yes this makes sense to me.I was trying to figure out if Tj had a steady worse case time across all loops
• user10326: :BTW isn't it (n(n-1))/2?
• jhulst: @user10326, You are correct, I did say approximately in the original answer but I've edited it to be more precise