ConceptTheory & Algos
Time constructible function
A function is time constructible if there exists a Turing machine that, given , outputs in time.
Know first
Named as a prerequisite by the lectures that define this. The number is how many say so. A grey one has no page yet.
Turing machine3Time complexity2Big O notation1Binary strings1Running time1Turing machine time complexity1
Opens up
Concepts that name this one as a prerequisite.
Lecturers
2Each in their own terms, from the easiest level.
Ryan O'Donnell
A function for which there exists a Turing machine that on inputs of length writes out symbols.Michael Sipser
Connections
9The lectures that define it or assume it, and the concepts next to it.