Are runtime bounds in P decidable? (answer: no)
The problem is undecidable. Specifically, you can reduce the halting problem to it as follows. Given an instance $(M,x)$ of the halting problem, construct a new machine $M&#39;$ that works as follows: on inputs of length $n$, it simulates $M$ on $x$ for $n$ steps. If $M$ accepts, loop for $n^2$ steps and stop; otherwise loop for $n^3$ steps and stop.

If $M$ halts on $x$ it does so in $t=O(1)$ steps, so the run time of $M&#39;$ would be $O(n^2)$. If $M$ never halts then the run time of $M&#39;$ is at least $n^3$.

Hence you can decide if $M$ accepts $x$ by deciding if the run time of $M&#39;$ is $O(n^2)$ or $O(n^3)$.