Time hierarchy theorem: Difference between revisions

Revision as of 23:09, 9 March 2025

Revision as of 23:13, 9 March 2025

Line 105:

'''Note 1.''' ''f''(''n'') is at least ''n'', since smaller functions are never time-constructible.<br>

'''Example.''' <math>\mathsf{DTIME}(n) \subsetneq \mathsf{DTIME} (n (\ln n)^2) </math>.

'''Example.''' There are problems solvable in time ''n''log²''n'' but not time ''n''. This follows by setting <math>f(n) = n\log n</math>, since ''n'' is in

:<math>o\left(n\log n\right).</math>

===Proof===