Zeitkonstruierbare Funktion

Eine Funktion $f:\mathbb{N}\to \mathbb{N}$ heißt zeitkonstruierbar, wenn $f(n)\ge n\log n$ und es eine Turingmaschine gibt, die bei Eingabe von $1^n$ in genau $O(f(n))$ Schritten hält (oft auch: $f(n)$ berechnet). Beispiele: $n^2,2^n$.