# Asympotic Estimates of Run-Times

• 11-30-2010
jturner38
Asympotic Estimates of Run-Times
Im trying to learn the Best Case, Average case, and Worse case Data. I kinda understand them and I kinda don't.

Example:

Code:

```for(i = 1; i<n, i++) for(j=0; j<n-1; j++)     if(A[j] > A[i]       {Switch = A[j];               A[j] = A[j+1];               A[j+1] = Switch;         }```
Would the Worse case be n^2 number of steps?
• 11-30-2010
User Name:
Think about how many times those loops will execute. It looks to me as if you're 1 off. Maybe (n +/- 1)^2 ?

EDIT: Also, note that there's no way for the loop to exit before the worst case is met, therefore best = average = worst.
• 11-30-2010
Codeplug
• 11-30-2010
jturner38
If Im 1 off. then (n-1)^2? Would that be correct since I could have a case where I might have to switch?
• 11-30-2010
jturner38
Actually it should be (n+1)^2 because (n+1)^2 = n^2 + O(n)?
• 12-01-2010
iMalc
Quote:

Originally Posted by jturner38
Im trying to learn the Best Case, Average case, and Worse case Data. I kinda understand them and I kinda don't.

Example:

Code:

```for(i = 1; i<n, i++) for(j=0; j<n-1; j++)     if(A[j] > A[i]       {Switch = A[j];               A[j] = A[j+1];               A[j+1] = Switch;         }```
Would the Worse case be n^2 number of steps?

Yes, and so would the Best and Average cases, albeit with different constant factors when executed in practice.

That code is borken by the way, both in terms of not compiling and not doing what one might expect.