Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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!

share|improve this question
3  
Bogosort! en.wikipedia.org/wiki/Bogosort –  Mark May 19 '11 at 9:31
5  
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? –  Gerry Myerson May 19 '11 at 10:35
4  
@Gerry: you could ask the question: for what problem is the best running time given in the literature the maximum? –  Peter Shor May 19 '11 at 11:15
3  
See the paper "Pessimal Algorithms and Simplexity Analysis" by Andrei Broder and Jorge Stolfi, google.com/… –  Ira Gessel May 19 '11 at 14:34
1  
See also CSTheory: "Polynomial-time algorithms with huge exponent" cstheory.stackexchange.com/questions/6660 –  Joseph O'Rourke May 19 '11 at 17:15
show 2 more comments

3 Answers 3

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

share|improve this answer
    
@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. –  Joseph O'Rourke May 19 '11 at 12:54
    
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. –  Joel David Hamkins May 19 '11 at 12:59
    
In particular, I dispute your claim that a quoted $\Theta()$ bound means that it is known that no algorithm can do better---we very rarely know such information. Rather, a quoted $\Theta()$ bound describes the known running time of a particular proposed algorithm. –  Joel David Hamkins May 19 '11 at 13:01
1  
@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 –  Tom Church May 19 '11 at 15:37
1  
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$. –  Joel David Hamkins May 19 '11 at 21:03
show 4 more comments

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, Number 1, 377-409

(2) Jeff Erickson. "New Lower Bounds for Convex Hull Problems in Odd Dimensions." SIAM J. Comput., 28 (1995) 1-9.


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

share|improve this answer
add comment

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

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

share|improve this answer
1  
Isn't it the case that in Tarski's original formulation, the complexity is not even elementary recursive? –  Thierry Zell May 19 '11 at 12:11
    
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. –  Joel David Hamkins May 19 '11 at 12:41
    
@Thierry: Yes, that's what the article says. –  Ricky Demer May 19 '11 at 16:56
    
@Joel: Yes, but it does not make it elementary recursive. –  Ricky Demer May 19 '11 at 16:57
    
Ah, I see now that "elementary recursive" is a very limited class: en.wikipedia.org/wiki/ELEMENTARY. –  Joel David Hamkins May 19 '11 at 22:31
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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