@eb: die O-notation beschreibt nicht die laufzeit eines algorithmus,
sondern das laufzeitverhalten. das bedeutet, es beschreibt, wie sich die
laufzeit in abhängigkeit von N verändert.
nehmen wir ein einfaches beispiel:
sub array {
 for (@_) { print "Element: $_\n" }
}
wie lange dieses programm braucht, weiss man nicht. das hängt ja vom rechner
ab und von der anzahl der elemente in @_. nennen wir die anzahl N.

die sub läuft bei N=1 eine bestimmte zeit lang x (wohl sehr kurz für ein
einziges print, aber unbekannt, weil wir den rechner nicht kennen). bei N=2
läuft die sub 2 mal solange, 2x. bei N=3 dreimal, 3x. usw. das heisst, die
laufzeit ist linear zur anzahl der elemente, deswegen O(N).

jetzt folgende sub:
sub array2 {
 for (@_) { print "Element: $_\n" }
 for (@_) { print "Zweiter Durchlauf: $_\n" }
}

auch diese sub hat O(N)! warum? weil die sub ganz sicher zwar länger braucht
als die erste, aber nochmal, hiergeht es um das laufzeitverhalten. bei N=1
haben wir eine bestimmte zeit x, bei N=2 wieder 2 mal x, N=3 3x.
auch hier steigt die laufzeit linear zu N.
klar, die zeit x ist in diesem fall höher als in der ersten sub. aber das
wollen wir ja gar nicht wissen, sondern wir wollen nur wissen, was passiert,
wenn ich mehr Elemente N habe.
man kann hier auch schreiben: O(2N), wenn man einen bezug zur der ersten sub
herstellen will. aber absolut gesehen ist die 2 eine konstante und
vernachlässigbar.

folgende sub:
sub array2 {
 for (@_) {
   for (@_) { print "Innerer Durchlauf: $_\n" }
 }
}
diese sub braucht bei einem element die laufzeit x (das print wird einmal
ausgeführt). bei zwei elementen hsben wir die laufzeit 2*2, also 4. bei drei
elementen ist x=3*3, also 9. aha, also quadratisches laufzeitverhalten, also
O(N*N) = O(N^2)

so hab ich das damals verstanden, als ich es gelernt habe. die meisten
fachbegriffe habe ich wieder vergessen; darin bin ich echt eine niete, aber
ich merk mir zumindest das prinzip, nachdem es funktioniert.