time-constructible function

Fetched 2026-10-26 (cache).

Datamuse reports no synonyms or antonyms for this word.

Noun

1. {{lb|en|computational complexity theory}} A function ''f'' from [[natural number]]s to [[natural number]]s with the [[property]] that ''f''(''n'') can be [[construct]]ed from ''n'' by a [[Turing machine]] in the time of order ''f''(''n''), whose [[purpose]] of such a [[definition]] is to [[exclude]] [[function]]s that do not [[provide]] an [[upper bound]] on the [[runtime]] of some [[Turing machine]].

Source: Wiktionary · CC BY-SA 4.0 (Wiktionary dump) · cached copy, not a rewrite.