for (int i=0; i < n; i++)			n(n-1) O(n^2)
 for (int j=0; j < n-i-1; j++)
  if (A[j] > A[j+1]) {
   string t = A[j];
   A[j] = A[j+1];
   A[j] = t;
  }


What is this?   ^^^^^^^^^^^

Bubble Sort


Q W E R T

Q W good

Q W E bad

Q E W R T

W R bad

Q E R W T

W T bad

Q E R T W

Q E bad

E Q R T W

Q R good
R T good
E Q good
Q R good
E Q good

If I have 5 items:

When i is

0:		n-i-1 = 4
1:		n-i-1 = 3
2:		n-i-1 = 2
3:		n-i-1 = 1
4:		n-i-1 = 0


The runtime is 0 + 1 + 2 + 3 + 4 + ... + (n-1).  What does that work out to be?

The sum of integers from 1 to n is:  n(n+1)/2 .

The sum of perfect squares from 1 to n^2 is:  n(n+1)(2n+1)/6 .

The sum of perfect cubes from 1 to n^3 is:  n^2 (n+1)^2 / 4.


The sum of 0+1+2+3+4+...+(n-1)  is the sum of integers from 1 to (n-1):

(n-1)n/2   = n^2/2 - n/2   = Theta (n^2).


Notice that the inner loop, on average runs in about n/2 steps.


1 2
4 3
5 5   10 steps /5 is about 2 steps on average


n x (n/2)  = Theta (n^2).


Merge Sort:

1.  Merge Sort first half.
2.  Merge Sort second half.
3.  Merge the halves.

We know that this in Theta (n lg n) time.

That lg is there because we keep halving the list.


If I merge two lists.  Then the time for the merge is Theta (n) time over the total size of the lists.


When I merge sort, that last merge that gives me the final answer is Theta (n) time.

Merging the first two quarters to get the first half is n/2.
Merging the last two quarters to get the second half is n/2, total n.

Similarly, merging the eighths is n.

Merging the sixteenths is n.

All the merges at all the steps each take n time.

And there are lg n steps, because we keep halving, total n lg n.