Worst known algorithm in terms of Big-O (more precisely Big-theta)? Hello,
I have been trying to find the worst algorithm in terms of it's Big-O function. By worst I mean n! is worse than n^2, n^n is worse than n!, etc. Essentially the worst algorithm would be the one with the fastest growing expression inside the Big-O notation.
I am aware that with the definition of Big-O if an algorithm is O(n^2), then it is also O(n!), so to be more precise I am really looking for the worst algorithm in terms of Big-Theta, because Big-Theta provides a more tight bound (I believe the tightest possible bound in terms of asymptotic analysis). I used Big-O in the title and explanation because I am not sure how many people are familiar with Big-Theta vs. Big-O.
I don't care at all from what branch of computing the algorithm is from (computational geometry, graph theory, etc.).
Thanks a lot!
 A: Of course there can be no "worst" algorithm, since for any
algorithm taking $p(n)$ steps on input of size $n$, we can
easily design another algorithm taking $2^{p(n)}$ steps,
which will be worse by the big-$O$ and big-$\Theta$
measures.
Meanwhile, the phenomenon of extremely long-running
computations is naturally related to the phenomenon of
fast-growing functions, such as the Ackermann diagonal
function,
whose values---and hence whose running times---are
extremely large in comparison with conventional algorithms.
For example, here is an algorithm that is likely to be
worse than any algorithm you may have considered. The
problem is to determine, on input $n$, the $A(n)$-th digit
of the decimal expansion of $\pi$, where $A(n)$ is the
Ackermann diagonal function. On input $n$, my proposed
algorithm would first compute $A(n)$, and then compute
$\pi$ to that many digits, and then output the
corresponding digit. The running time of this algorithm
will exceed the Ackermann diagonal function, but it is not
clear how one could improve the algorithm to make it
faster.
But perhaps you meant to inquire merely about feasible
algorithms, that is, algorithms that we will actually want
to undertake. In this case, of course, even the exponential
algorithms that seem to be required for NP problems would
be too hard, and we would want to stay within the
polynomial hierarchy. Even $n^3$ algorithms are not really
feasible on large input.
(But indeed, I go further, if you are truly interested only
in actually feasible, practical algorithms, then the
big-$O$ and big-$\Theta$ concepts are not the right
concept, since even constant time $O(1)$ algorithms can be
unfeasible, if the constant is very large. The whole point
of big-$O$ and big-$\Theta$ is to look at asymptotic
behavior of the algorithms on extremely large input, and
this takes us immediately out of the actually feasible
category.)
A: Tarski's decision procedure for sentences in the first-order theory of real closed fields
users.cs.duke.edu/~reif/paper/benor/realclosed.pdf
A: I think the question needs to be sharpened to exclude algorithms that compute
(or even involve)
combinatorially complex structures.
For example, the convex hull of $n$ points in $\mathbb{R}^d$ has size $\Theta(n^{\lfloor d/2 \rfloor})$
for fixed $d$.
There is an asymptotically optimal algorithm (due to Chazelle (1)) to compute this hull
in time $O( n \log n + n^{\lfloor d/2 \rfloor} )$.
So one could exceed any power of $n$ in the time complexity by selection of a sufficiently
large $d$.
So you need to specify that the algorithm is a decision procedure,
outputting only one bit, Yes or No.
But even here, there is no upper bound on the "worst" algorithm time complexity.
Again consider the convex hull in $\mathbb{R}^d$, $d$ fixed, and ask:
(a) Is the hull simplicial?
or (b) Does the hull have exactly $F$ facets?
Jeff Erickson showed (2) that, even for these decision questions,
$\Omega( n \log n + n^{\lceil d/2 \rceil -1} )$ time is needed,
matching the known upper bounds for odd $d$.

(1) Bernard Chazelle.
"An optimal convex hull algorithm in any fixed dimension."
Discrete & Computational Geometry,
Volume 10 (1993), Number 4, 377–409.
Zbl 0786.68091
(2) Jeff Erickson.
"New Lower Bounds for Convex Hull Problems in Odd Dimensions."
SIAM J. Comput., 28 (1999), 1198–1214.
Zbl 0939.68047

An irrelevant aside: I coauthored an algorithm with time complexity $O(n^{42})$. :-)
