O Notation zu InsertionSort richtig berechnen

[seux]

Hallo,
ich möchte gerne den WorstCase Fall zu folgendem Algorithmus(InsertionSort) bestimmen. Ich hab die rechnung mal angefangen, weiß allerdings nicht weiter.

Hier erstmal der Code in Java:

@SuppressWarnings({ "rawtypes", "unchecked" })
	public static <T extends Comparable> void doInsertionSort(ArrayList<T> a) {

		for(int i = 1; i < a.size(); i++) {

			T currentValue = a.get(i);

			int j = i;

			while(j > 0) {

				if(a.get(j-1).compareTo(currentValue) >= 0) {

					a.set(j, a.get(j-1));

					j--;

				} else {
					break;
				}

				a.set(j, currentValue);
			}
		}

So, meine Rechnung sieht bisher wie folgt aus:
$O(\sum\limits_{i=1}^n ( O(1) + O(1) + O(\sum\limits_{j=0}^i (O(1) + O(1) + O(1)) ) + O(1)))$
$O(\sum\limits_{i=1}^n + O(\sum\limits_{j=0}^i O(1) ))$
$O(\sum\limits_{i=1}^n + O(i))$

Ist das überhaupt richtig? Und wie würde es weitergehen?

gruß seux

[icarus2]

Durch Inspektion des Codes sieht man, dass die innere Schleife jeweis hoechstens i mal durchlaufen wird mit $i = 1, 2, \ldots, n$, wobei $n := a.size()-1$. Du bekommst dann folgende Reihe (den Grenzwert kann man einfach mittels Induktion beweisen):
$\sum\limits_{i=1}^n i = \frac{n(n+1)}{2} \in O(n^2)$