DTIME

In computational complexity theory, DTIME (or TIME) is the computational resource of computation time for a deterministic Turing machine. It represents the amount of time (or number of computation steps) that a "normal" physical computer would take to solve a certain computational problem using a certain algorithm. It is one of the most well-studied complexity resources, because it corresponds so closely to an important real-world resource (the amount of time it takes a computer to solve a problem).

The resource DTIME is used to define complexity classes, sets of all of the decision problems that can be solved using a certain amount of computation time. If problem instances of input size n can be solved in ⁠${\displaystyle O(f(n))}$⁠, the problem is in the complexity class ⁠${\displaystyle {\mathsf {DTIME}}(f(n))}$⁠ (or ⁠${\displaystyle {\mathsf {TIME}}(f(n))}$⁠). There is no restriction on the amount of memory space used, but there may be restrictions on some other complexity resources (like alternation).