Is it true that every algorithm $f(x)\in{\mathcal O}(BB(n))$?

Question

Assuming there is an algorithm with the runtime $f(n)$. Define $BB(n)$ as the BusyBeaver function.

The algorithm must always returns the same output for the same input, but it might use some internal random (e.g. a random pivot selection of QuickSort) which might change the required calculation steps. The algorithm must halt for all inputs. Is the following statement true for all these algorithms?

$f(n)\in{\mathcal O}(BB(n))$?

I think it is true, because $BB(n)$ grows faster than every calculatable function, but I'm not sure if this is a good reason.

Thank you very much

Kevin

Answer 1

It is indeed, and due to the reason you say.

Let $M(n)$ be TM with runtime $f(n)$. Then it would be possible to build another machine $C$ which does the following:

• On input $n$, simulate $M(n)$ and for each step given by $M$ add $1$ to a counter.

Then $C(n)$ computes the runtime $f(n)$, and it certainly effectively computable.

Thus as $BB(n)$ asymptotically dominates every computable function, it must be the case that $f(n)\in \mathcal{O}(BB(n))$.

We have ignored the possible randomness, but to account for that we can restrict the analysis to the worst case running time, which is also computable (we can enumerate all possible paths that the algorithm may follow on input $n$, which are finite, since otherwise it would possibly not halt, then repeat the procedure for every path and output the max).