We discuss the following family of problems, parameterized by integers C\geq 2 and D\geq 1: Does a given one-tape non-deterministic q-state Turing machine make at most Cn+D steps on all computations on all inputs of length n, for all n?
Assuming a fixed tape and input alphabet, we show that these problems are co-NP-COMPLETE and we provide good non-deterministic and co-non-deterministic lower bounds. Specifically, these problems can not be solved in o(q^{(C-1)/4}) non-deterministic time by multi-tape Turing machines. We also show that the complements of these problems can be solved in O(q^{C+2}) non-deterministic time and not in o(q^{(C-1)/2}) non-deterministic time by multi-tape Turing machines.
Up to constant factors in the exponents all of the above results hold also if we restrict our input only to deterministic one-tape Turing machines.