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.
Simple and practical deterministic algorithm, complicated running time
ds.algorithms;soft question;recreational
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).