DTIME

In complexity theory is DTIME ( f ) or short TIME ( f) for the amount of time complexity classes in terms of a deterministic Turing machine. If a concrete function f indicated, it means: DTIME ( f) is the class of those decision problems that are solvable on a deterministic Turing machine in O ( f) time. Note that if you specify a concrete function f is the name DTIME ( f) is a single complexity class, while the use of a function f unspecified the name DTIME ( f) a whole lot of complexity classes says. Moreover, one can see from usually of constant factors in the function definition of f and is thus DTIME (f) = DTIME (O ( f)). The justification for this approach provides, inter alia, the linear speedup theorem.

One uses the notation DTIME ( f ) for all time classes that do not have their own name, such as in the time hierarchy records. In addition, it may be used to define more concrete complexity classes: for example, the important class P is defined as follows: