5 votes

Is any function between $n$ and $n\log n$ time-constructible on a 1-tape TM?

[EDIT: This result was already observed in Corollary 4.6 of the following paper: Gajser, David, Verifying time complexity of Turing machines, Theor. Comput. Sci. 600, 86-97 (2015). ZBL1329.68111.] ...

Only top scored, non community-wiki answers of a minimum length are eligible