Langsamer als Polynom aber schneller als Logarithmus?
-
Gibt es eine Funktion die schneller wächst als der Logarithmus aber langsamer als jedes Polynom? Formal:
Gibt es eine Funktion f:N→N mit f(n)=O(n^α) für jedes α>0 und f(n)=ω(log(n))?
Falls es kein solches f gibt: Ist folgende Argumentation valide? Wenn die Laufzeit eines Algorithmus in O(n^α) für jedes α>0 ist, dann ist seine Laufzeit in O(log(n)).
-
p(Log n), wobei p ein beliebiges polynom ist liegt (für die meisten polynome p) echt dazwischen. Wenn man nix besseres findet schreibt man manchmal auch O(n^epsilon).
-
log(n)^(1+epsilon)
-
Klingt einleuchtend, Danke