Simple and practical deterministic algorithm, complicated running time

Question

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.

Answer 1

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

Answer 2

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

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

Answer 3

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

Answer 4

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.

Answer 5

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.