Um nochmal zu der Anfangsfrage zu kommen, ob man in N oder R ist. Das ist eigentlich wurscht. In der Regel betrachtet man in der Informatik bei Laufzeit- und Platzbedarfabschätzungen Funktionen f:N -> N. Liegt ganz einfach daran, weil 7,543 Rechenoperationen nicht so oft vorkommen, und ein Speicherplatzbedarf von 3,543432 Byte macht auch keinen Sinn.
Man kann aber für die Argumentation ob "f = O(g)" durchaus erstmal annehmen, dass man Funktionen von R nach R hat, und Techniken aus der Analysis anwenden, um das zu zeigen oder zu widerlegen. Ob man nun so eine Treppenfunktion betrachtet, oder eine Kurve, die "glatt dadurch geht", ist für das Ergebnis nicht relevant. Aber meistens braucht man das nicht
.
Wenn man die Grundvorlesungen hinter sich hat, sind eh fast alle Algorithmen in O(N), NlogN und N^2. Und dann gibts natürlich die, die jenseits von Gut und Böse sind, also N!, 2^N und sowas. Aber da zeigt man dann nur noch, dass diese Probleme "NP-vollständig" sind und begnügt sich damit, dass man das nicht exakt in vernünftiger Zeit lösen kann