Is every recursive set's worst-case time complexity a total recursive function?
1
-
4$\begingroup$ There is no such thing as the "worst-case time complexity" of any given recursive set. First, given any algorithm for the set and any $n_0$, you can modify the algorithm so that it takes time $n$ for all input lengths $n\le n_0$. Second, you can speed-up any Turing machine by any constant factor by increasing the working alphabet. These already show that at best, worst-case time complexity can be defined as an asymtotic growth rate, disregarding small inputs and constant factors. But even that fails badly for some sets due to en.wikipedia.org/wiki/Blum%27s_speedup_theorem. $\endgroup$– Emil JeřábekNov 14 at 9:40
Add a comment
|