Is determining if a Turing machine runs in constant time decidable if one assumes it halts?
This answer is for the following version of the question:


  Can we decide whether an algorithm runs in constant time (that is, within $N$ steps, for some $N$), given that it is guaranteed to always halt?


This is not decidable. Given a Turing machine $T$, construct a new Turing machine $M$ which on input $t$ runs $T$ for up to $t$ steps. Then $M$ runs in constant time iff $T$ halts.