Gibt es O(1/n)-Algorithmen?
Als Erstes sollte man sich bewusst werden, was genau die Komplexitätsklasse über einen Algorithmus aussagt.
Ich gehe mal davon aus, dass hier O(1/n) die Worst-Case Komplexität sein soll.
Angenommen es existiert die Klasse O(1/n), dann gilt für alle Algorithmen die Element aus jener Klasse sind, dass diese nach obenhin durch die Funktion f(n) = (1/n) beschränkt sind.
Man erkennt, dass n und f(n) antiproportional zueinander sind. In diesem Falle würde es bedeuten, dass je mehr Rechenschritte (n) der Algorithmus benötigt, umso weniger Zeit es Bedarf diese zu vollenden (f(n)).
Wählen wir nun n und (n + 1):
f(n + 1) - f(n) = (1 / (n + 1)) - (1 / n), da f(n) > f(n + 1) gilt: f(n + 1) - f(n) < 0
Da wir davon ausgehen können, dass jeder Rechenschritt eine gewisse Zeit (größer 0) benötigt, macht die Aussage f(n + 1) - f(n) < 0 bzw. f(n) > f(n + 1) keinen Sinn und steht im Widerspruch mit der Existenz der Komplexitätsklasse O(1/n).
Somit existiert die Klasse O(1/n) (zumindest in der Praxis) nicht.