Definition:Time-Constructible Function/Definition 2

Definition

Let $f$ be a function.

Let there exist a positive integer $n_0$ and a Turing machine $M$ such that:

Given a string $1^n$ consisting of $n$ instances of $1$, $M$ outputs the binary representation of $\map f n$ in $\map \OO {\map f n}$ time.

Then $f$ is time-constructible.

Also see

• Equivalence of Definitions of Time-Constructible Functions