The complexity class DTIME

DTIME[math]\displaystyle{ (f(n)) }[/math] is the class of decision problems that can be solved by a deterministic Turing machine in time [math]\displaystyle{ O(f(n)) }[/math].

Note that the time hierarchy theorem implies that relatively modest increases in [math]\displaystyle{ f(n) }[/math] strictly increases the size of the complexity class DTIME[math]\displaystyle{ (f(n)) }[/math]. More precisely, DTIME[math]\displaystyle{ (f(n)) }[/math] is strictly contained in DTIME[math]\displaystyle{ (f(n)\log f(n) \log \log f(n)) }[/math].