Is every recursive set's worst-case time complexity a total recursive function?

  • 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$ Nov 14 at 9:40


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.