0
$\begingroup$

We’ve all seen this: Hierarchy of time complexities

Can we get worse?

Part 1: Can mathematical operations of increasing orders of growth be generated, with or without Knuth’s up-arrow notation?

Part 2: If they can, can algorithms of arbitrary complexities be systematically generated?

Part 3: If such algorithms can be generated, what about programs implementing those algorithms?

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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 set of Turing machines which have runtime bounded by a given function is not computable. So you need a trick ...

So the only bound on runtime is the trivial one, that runtime has to be computable.

(If we drop the requirement that our machines halt on all inputs, things get more complicated - see the Busy Beaver function.)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.