18
$\begingroup$

Very often, if the running time of an algorithm is a complicated expression, the algorithm itself is also complicated and impractical. Each of the cube roots and $\log \log n$ factors in the asymptotic running time tends to add complexity to the algorithm and also hidden constant factors to the running time.

Do we have striking examples in which this rule of thumb fails?

Of course it is easy to find examples of algorithms that are very difficult to implement even though they happen to have a very simple worst-case running time. But what about the converse?

Do we have examples of very simple and practical deterministic algorithms that are easy to implement but happen to have a very complicated expression as its worst-case asymptotic running time?

Please note the keywords "deterministic" and "worst-case"; the analysis of simple randomised algorithms fairly easily leads to complicated expressions.

Of course what is "complicated" is a matter of taste. Anyway, I would prefer to see an expression that is far too ugly to put in the title of your paper. And I would prefer a complicated function of one natural parameter (input size, number of nodes, etc.).


PS. I thought I would not make this a "big-list question", and not CW. I'd like to find a single excellent example (if it exists at all). Hence please post another answer only if you think that it is "better" than any of the answers so far.

$\endgroup$
  • 2
    $\begingroup$ Does the AKS primality testing algorithm qualify as an answer? I'm hesitating because the "complicatedness" of its running time is, in some sense, a result of the pseudorandomness of the distribution of primes... $\endgroup$ – arnab Nov 16 '10 at 22:21
  • $\begingroup$ My feeling is that the worst-case is in most cases something that causes "runs over everything" and everything is the thing we measure runtime in. So, naturally, easy algorithms have easy WC-runtimes. Complicated runtimes come up if we try to shave one tiny bit off by some trick. But your question is interesting; I am certainly curious to see wether my feeling is right. $\endgroup$ – Raphael Nov 16 '10 at 22:29
  • $\begingroup$ @arnab: Thanks, AKS is a good idea. But I'm not sure if we can call it "practical"? $\endgroup$ – Jukka Suomela Nov 16 '10 at 22:36
  • $\begingroup$ Do message-passing schemes like survey propagation, constraint propagation or sequential TRW count as "algorithms"? Easy to implement, runtime is hard to predict $\endgroup$ – Yaroslav Bulatov Nov 17 '10 at 2:14
  • $\begingroup$ Oops, I always like the Pollard's rho method, it is simple and practical, and the analysis is really hard, but the randomness of the algorithm make it unqualified as an answer to the post... $\endgroup$ – Hsien-Chih Chang 張顯之 Nov 17 '10 at 4:24
20
$\begingroup$

The best example I can think of is an algorithm (described below) to compute the $k$-level in an arrangements of $n$ lines in the plane, i.e. the polygonal line formed by the points that have exactly $k$ lines vertically above it. This is not the most efficient algorithm known for the problem. There are more efficient algorithms with simpler complexities, but I believe this one is more practical than most (if not all) of them. The analysis is probably not tight, because it uses the $k$-level complexity, which is a famous open problem (I think all other terms in the analysis are tight). Even still, I doubt improved bounds for $k$-level would make the running time much simpler. I'll assume $k=n/2$ to write the complexity as a function of $n$ alone.

The algorithm is based on the line sweep paradigm and uses two $(\log n)$-ary kinetic tournaments as kinetic priority queues. Insertions and deletions are performed when a line goes above or below the $k$-level, moving a line from one kinetic tournament to the other. Therefore, there are $O(n^{4/3})$ insertions and deletions (using Dey's bound for the $k$-level complexity). Each event is processed in $O(\log n)$ time and there are $O(n^{4/3} \alpha(n) \log n / \log \log n)$ events (the $\alpha(n)$ comes from the complexity of the upper envelope of arrangements of line segments, while the $\log n / \log \log n$ comes from the height of a $(\log n)$-ary tree). The total running time is

$$O(n^{4/3} \alpha(n) \log^2 n / \log \log n).$$

Please check Timothy Chan's manuscript http://www.cs.uwaterloo.ca/~tmchan/lev2d_7_7_99.ps.gz for more details and references. The $1/\log \log n$ factor can be removed by using a binary (intead of $(\log n)$-ary) kinetic tournament, but it actually speeds up the kinetic priority queue in the tests that I performed. The complexity should get a little uglier and worse (while the algorithm will still be practical) if a kinetic heap is used instead of a kinetic tournament (a $\log$ inside a square root should show up).

$\endgroup$
  • $\begingroup$ Excellent example, thanks! This isn't going to be easy to beat. :) $\endgroup$ – Jukka Suomela Nov 16 '10 at 22:45
  • 1
    $\begingroup$ This algorithm is slower in practice than the randomized algorithms, which are pretty easy to implement (as somebody that implemented one of these algorithms (see my paper "Taking a walk in a planar arrangement".) $\endgroup$ – Sariel Har-Peled Nov 18 '10 at 20:59
  • $\begingroup$ I have accepted this answer as it seems to be closest to what I had in mind. But if anyone has any fresh ideas, I would be happy to hear! $\endgroup$ – Jukka Suomela Nov 22 '10 at 14:10
24
$\begingroup$

The union-find data structure operations seem to meet your criteria:

http://en.wikipedia.org/wiki/Disjoint-set_data_structure

$\endgroup$
  • 2
    $\begingroup$ Indeed, I posted the same answer but deleted it after I noticed you beat me to it. :) Simple and elegant algorithm that a non-theorist might even discover, but inverse Ackermann amortized complexity. $\endgroup$ – Warren Schudy Nov 16 '10 at 23:58
  • $\begingroup$ Well, $O(\alpha(n))$ time doesn't look that "complicated" if you compare it to $O(n^{4/3} \alpha(n) \log^2 n / \log \log n)$ in Guilherme's answer. :) $\endgroup$ – Jukka Suomela Nov 17 '10 at 8:26
  • $\begingroup$ The ratio of algorithm length to proof complexity for union-find is probably unbeatable -- all three operations are what, nine lines of code? $\endgroup$ – Neel Krishnaswami Nov 17 '10 at 16:15
  • 1
    $\begingroup$ I don't think the question is about a simple and practical algorithm with complex analysis. I think the question is about a simple and practical algorithm with complex running time, that is, the actual expression obtained for the upper bound. $\endgroup$ – Guilherme D. da Fonseca Nov 17 '10 at 20:53
6
$\begingroup$

Simplex algorithm. Easy to implement and works wonderfully in practice but is a mess to analyze theoretically.

$\endgroup$
  • $\begingroup$ Yes, it is hard to analyse, but is there an analysis that has concluded that the running time of Simplex is bounded by a certain complicated function of $n$? $\endgroup$ – Jukka Suomela Nov 17 '10 at 8:28
  • $\begingroup$ actually simplex is known to take exponential time in the worst-case via the Klee-Minty construction. It's not, I think, an example of what Jukka is asking about $\endgroup$ – Suresh Venkat Nov 17 '10 at 17:12
  • 1
    $\begingroup$ Maybe I should have said the simplex method rather than the simplex algorithm. The Klee-Minty cube and its variations work for some vanilla pivoting rules. But ,for example, the random facet pivoting rule has an crazy upper and (recent) lower bound. Gil Kalai had a nice blog entry on the recent results. gilkalai.wordpress.com/2010/11/09/… $\endgroup$ – Mohit Singh Nov 17 '10 at 19:56
  • $\begingroup$ good point, Mohit. I was confused as well. $\endgroup$ – Suresh Venkat Nov 18 '10 at 23:08
2
$\begingroup$

I'm not sure if you consider this "practical" but it is a famous open problem. Paul Erdos said about Collatz conjecture: “Mathematics is not yet ready for such problems”

Collatz procedure: while (x != 1) { if x is odd, x = 3x + 1; else x = x/2}. A famous conjecture is that the procedure always terminates with $x=1$. I'm not aware of simple run-time complexity of this algorithm.

$\endgroup$
  • $\begingroup$ And what is the problem solved by this algorithm...? $\endgroup$ – Jukka Suomela Nov 16 '10 at 22:38
  • $\begingroup$ It suggests looking for novel run-time analysis techniques. $\endgroup$ – Mohammad Al-Turkistany Nov 16 '10 at 22:50
  • 2
    $\begingroup$ you could then say that a brute-force search for a proof of the Collatz conjecture also motivates "novel run-time analysis techniques"; in both cases the algorithm is just mindlessly exploring a digraph. The Collatz conjecture is fun, but I don't think this is an interesting example of "an algorithm". $\endgroup$ – Niel de Beaudrap Nov 17 '10 at 18:35
2
$\begingroup$

This example, while not meeting the letter of your request may be of interest because it bears some spiritual affinity. Specifically, the question of sorting stacks of pancakes and burnt pancakes by reversals.

http://en.wikipedia.org/wiki/Pancake_sorting

One area of application is to computational biology (genetics) where questions about genome rearrangements can be couched in terms of the distance between permutations using reversals of pieces of the permutations subject to various rules.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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