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?

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.

http://en.wikipedia.org/wiki/Time_complexity
http://en.wikipedia.org/wiki/Big_O_notation

For big-O, it's O(n²)

gg

If Im 1 off. then (n-1)^2? Would that be correct since I could have a case where I might have to switch?

Actually it should be (n+1)^2 because (n+1)^2 = n^2 + O(n)?

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.