Constructible function

In complexity theory, a time-constructible function is a function f from natural numbers to natural numbers with the property that f(n) can be constructed from n by a Turing machine in the time of order f(n). The purpose of such a definition is to exclude functions that do not provide an upper bound on the runtime of some Turing machine.^[1]

^ Goldreich, Oded (2008). Computational Complexity: A Conceptual Perspective. Cambridge University Press. pp. 130, 139. ISBN 978-0-521-88473-0.

[:0-1] Goldreich, Oded (2008). Computational Complexity: A Conceptual Perspective. Cambridge University Press. pp. 130, 139. ISBN 978-0-521-88473-0.

[1]