nein, N ist nicht die Laufzeit; N ist eine Menge

Ist gibt auch nicht nur O(N) vondern auch \Theta(N), o(N) (kleines o), \Omega(N), etcpp...

das Symbol vor (N) sagt, wie die Funktion wächst...

Wenn man sagt, dass ein Algorithmus in O(N) läuft, dann heißt das in Wirklichkeit:

Eine Funktion f, die den Algorithmus beschreibt, wächst nicht schneller als die Funktion g mit g(x) = x bzw. man kann schreiben

f ist Element von O(g) = f <= g

Wenn was in o(N) läuft, kann man sagen

f ist Element von o(g) = f < g; also f wächst langsamer als g

usw.