2
$\begingroup$

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!

Improve this question
$\endgroup$
8
  • 6
    $\begingroup$ Bogosort! en.wikipedia.org/wiki/Bogosort $\endgroup$
    – Mark
    Commented May 19, 2011 at 9:31
  • 11
    $\begingroup$ I'm not convinced this is a real question. Isn't it the case that given any algorithm one can find another that's significantly worse? $\endgroup$
    – Gerry Myerson
    Commented May 19, 2011 at 10:35
  • 4
    $\begingroup$ @Gerry: you could ask the question: for what problem is the best running time given in the literature the maximum? $\endgroup$
    – Peter Shor
    Commented May 19, 2011 at 11:15
  • 5
    $\begingroup$ See the paper "Pessimal Algorithms and Simplexity Analysis" by Andrei Broder and Jorge Stolfi, google.com/… $\endgroup$
    – Ira Gessel
    Commented May 19, 2011 at 14:34
  • 4
    $\begingroup$ See also CSTheory: "Polynomial-time algorithms with huge exponent" cstheory.stackexchange.com/questions/6660 $\endgroup$
    – Joseph O'Rourke
    Commented May 19, 2011 at 17:15

3 Answers 3

Reset to default
8
$\begingroup$

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.)

Improve this answer
$\endgroup$
10
  • $\begingroup$ @Joel: Concerning your first sentence, wouldn't it be more natural to focus on the time complexity of any algorithm that solves a particular problem, rather than on the time complexity of a specific algorithm? So usually a quoted $\Theta()$ bound means that no algorithm can do better, and some algorithm achieves that bound. $\endgroup$
    – Joseph O'Rourke
    Commented May 19, 2011 at 12:54
  • $\begingroup$ Joseph, the running-time concept is a feature of the algorithm, not of the problem that the algorithm solves. Indeed, we very rarely have information about the best possible time bound to solve a given problem. For example, knowing such information for certain problems would enable us to solve the P vs. NP problem. $\endgroup$
    – Joel David Hamkins
    Commented May 19, 2011 at 12:59
  • 1
    $\begingroup$ @Joel, re: "it is not clear how one could improve the algorithm to make it faster." As soon as $n>3$ a huge speedup will be provided by using a spigot algorithm, which computes individual digits of $\pi$ without computing the preceding digits. en.wikipedia.org/wiki/Bailey-Borwein-Plouffe_formula $\endgroup$
    – Tom Church
    Commented May 19, 2011 at 15:37
  • 2
    $\begingroup$ Tom, yes, that would be faster, a polynomial time speed-up. But this is a actually a very mild improvement in light of the huge cost of computing $A(n)$, which dominates this algorithm. After all, the Ackermann function grows so rapidly that $A(n)$, $\log(A(n))$, $2^{A(n)}$ and even $2\uparrow A(n)$ all seem basically in the same ballpark (for example, these differences matter far far less than simply going to $A(n\pm 1)$), and so it is the difficulty of computing $A(n)$ that matters here, swamping any difficulty of computing $\pi$. $\endgroup$
    – Joel David Hamkins
    Commented May 19, 2011 at 21:03
  • 1
    $\begingroup$ There's no reason that computing the A(n)th digit of pi necessarily requires computing A(n). That would be like saying that computing A(n) mod 2 requires computing A(n), which it doesn't seem to (it appears to always be 1, but I haven't done all the necessary math.) Both are of the form f(A(n)). I agree that there's probably no shared structure, but that doesn't lead to a proof that there's no shared structure. $\endgroup$
    – clahey
    Commented Jun 16, 2015 at 18:21
6
$\begingroup$

Tarski's decision procedure for sentences in the first-order theory of real closed fields

users.cs.duke.edu/~reif/paper/benor/realclosed.pdf

Improve this answer
$\endgroup$
5
  • 1
    $\begingroup$ Isn't it the case that in Tarski's original formulation, the complexity is not even elementary recursive? $\endgroup$
    – Thierry Zell
    Commented May 19, 2011 at 12:11
  • $\begingroup$ Thierry, Tarski's original algorithm was an elimination of quantifiers argument: given a sentence, he applied his recursive quantifier elimination procedure and ended up with a quantifier-free assertion, whose truth can be easily decided. This makes his original algorithm definitely recursive, even primitive recursive, but it was horribly iterated exponential time. $\endgroup$
    – Joel David Hamkins
    Commented May 19, 2011 at 12:41
  • $\begingroup$ @Thierry: Yes, that's what the article says. $\endgroup$
    – user5810
    Commented May 19, 2011 at 16:56
  • $\begingroup$ @Joel: Yes, but it does not make it elementary recursive. $\endgroup$
    – user5810
    Commented May 19, 2011 at 16:57
  • $\begingroup$ Ah, I see now that "elementary recursive" is a very limited class: en.wikipedia.org/wiki/ELEMENTARY. $\endgroup$
    – Joel David Hamkins
    Commented May 19, 2011 at 22:31
6
$\begingroup$

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})$. :-)

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .