# The complexity class DTIME

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
DTIME$(f(n))$ is the class of decision problems that can be solved by a deterministic Turing machine in time $O(f(n))$.
Note that the time hierarchy theorem implies that relatively modest increases in $f(n)$ strictly increases the size of the complexity class DTIME$(f(n))$. More precisely, DTIME$(f(n))$ is strictly contained in DTIME$(f(n)\log f(n) \log \log f(n))$.