New answers tagged


On the one hand, every algorithm (by which I will mean a Turing machine which halts on all inputs) has computable runtime. On the other hand, by diagonalization for every computable function $f$ there is a computable set $X_f$ such that no Turing machine computing $X_f$ runs in time $O(f)$. This is a good exercise. The obvious approach doesn't work: the ...


Yes, of course. $2^{f(n)}$ is asymptotically larger than $f(n)$, so you can come up with an unending sequence of larger and larger running times. The answer to your other questions are also yes, by the time hierarchy theorem.

Top 50 recent answers are included