Is there an example of an algorithm whose time complexity is strictly larger than Ackermann's function?
$\begingroup$
$\endgroup$
Add a comment
|
$\begingroup$
$\endgroup$
1
$A(n,n)$ is computable. So a trivial algorithm with complexity $O(A(n,n)^2)$ is the following:
- Compute $x = A(n,n)$.
- Loop $x^2$ times, doing nothing.
-
1$\begingroup$ A(n+1, n+1) has a hugely higher time complexity. $\endgroup$ – gnasher729 Nov 25 '20 at 14:01
