Simple and practical deterministic algorithm, complicated running time 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.
The union-find data structure operations seem to meet your criteria:

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