<p>The union-find data structure operations seem to meet your criteria:</p>

<p><a href="http://en.wikipedia.org/wiki/Disjoint-set_data_structure">http://en.wikipedia.org/wiki/Disjoint-set_data_structure</a></p>

CC BY-SA 2.5
2010-11-16T23:58:23.693Z
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.
Warren Schudy
CC BY-SA 2.5
2010-11-17T08:26:02.837Z
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. :)
Jukka Suomela
CC BY-SA 2.5
2010-11-17T16:15:35.837Z
The ratio of algorithm length to proof complexity for union-find is probably unbeatable -- all three operations are what, nine lines of code?
Neel Krishnaswami
CC BY-SA 2.5
2010-11-17T20:53:42.623Z
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.
Guilherme D. da Fonseca
CC BY-SA 2.5
2010-11-16T23:43:38.443Z
2010-11-16T23:43:38.443Z
Kevin Wortman
<p>Simplex algorithm. Easy to implement and works wonderfully in practice but is a mess to analyze theoretically.</p>

CC BY-SA 2.5
2010-11-17T08:28:57.777Z
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$?
Jukka Suomela
CC BY-SA 2.5
2010-11-17T17:12:48.760Z
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
Suresh Venkat
CC BY-SA 2.5
2010-11-17T19:56:10.293Z
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. http://gilkalai.wordpress.com/2010/11/09/subexponential-lower-bound-for-randomized-pivot-rules/
Mohit Singh
CC BY-SA 2.5
2010-11-18T23:08:55.277Z
good point, Mohit. I was confused as well.
Suresh Venkat
CC BY-SA 2.5
2010-11-17T01:41:07.000Z
2010-11-17T01:41:07.000Z
Mohit Singh
<p>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. </p>

<p><a href="http://en.wikipedia.org/wiki/Pancake_sorting" rel="nofollow">http://en.wikipedia.org/wiki/Pancake_sorting</a></p>

<p>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.</p>

CC BY-SA 2.5
2010-11-18T20:46:47.937Z
2010-11-18T20:46:47.937Z
Joseph Malkevitch
<p>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”</p>

<p>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.</p>

CC BY-SA 2.5
2010-11-16T22:38:13.493Z
And what is the problem solved by this algorithm...?
Jukka Suomela
CC BY-SA 2.5
2010-11-16T22:50:37.007Z
It suggests looking for novel run-time analysis techniques.
Mohammad Al-Turkistany
CC BY-SA 2.5
2010-11-17T18:35:44.540Z
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".
Niel de Beaudrap
CC BY-SA 2.5
2010-11-16T22:10:22.220Z
2010-11-16T22:34:58.610Z
2010-11-16T22:34:58.610Z
Mohammad Al-Turkistany
<p>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.</p>

<p>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</p>

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

<p>Please check Timothy Chan's manuscript <a href="http://www.cs.uwaterloo.ca/~tmchan/lev2d_7_7_99.ps.gz">http://www.cs.uwaterloo.ca/~tmchan/lev2d_7_7_99.ps.gz</a> 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).</p>

CC BY-SA 2.5
2010-11-16T22:45:09.600Z
Excellent example, thanks! This isn't going to be easy to beat. :)
Jukka Suomela
CC BY-SA 2.5
2010-11-18T20:59:02.417Z
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".)
Sariel Har-Peled
CC BY-SA 2.5
2010-11-22T14:10:39.397Z
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!
Jukka Suomela
CC BY-SA 2.5
2010-11-16T22:32:56.783Z
2010-11-17T00:12:04.257Z
2010-11-17T00:12:04.257Z
Guilherme D. da Fonseca
<p>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.</p>

<p>Do we have striking examples in which this rule of thumb fails?</p>

<p>Of course it is easy to find <a href="http://dx.doi.org/10.1007%2FBF02574703">examples</a> 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?</p>

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

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

<p>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 <em>one</em> natural parameter (input size, number of nodes, etc.).</p>

<hr>

<p>PS. I thought I would <em>not</em> 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.</p>

CC BY-SA 2.5
2010-11-16T22:21:24.863Z
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...
arnab
CC BY-SA 2.5
2010-11-16T22:29:41.127Z
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.
Raphael
CC BY-SA 2.5
2010-11-16T22:36:26.160Z
@arnab: Thanks, AKS is a good idea. But I'm not sure if we can call it "practical"?
Jukka Suomela
CC BY-SA 2.5
2010-11-17T02:14:13.637Z
Do message-passing schemes like survey propagation, constraint propagation or sequential TRW count as "algorithms"? Easy to implement, runtime is hard to predict
Yaroslav Bulatov
CC BY-SA 2.5
2010-11-17T04:24:40.137Z
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...
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2010-11-17T05:41:12.330Z
Interesting that the two most popular answers involve running times that have inverse Ackermann terms. So "inverse Ackermann" is tantamount to "hard to analyze"
Suresh Venkat
CC BY-SA 2.5
2010-11-17T08:31:52.597Z
@Yaroslav: Everything counts (as long as it's practical and deterministic), but please note that I'm looking for something that *has* been analysed successfully, and the end result just happens to be a messy, complicated function of $n$.
Jukka Suomela
<ds.algorithms><soft-question><recreational>
Simple and practical deterministic algorithm, complicated running time
Jukka Suomela
# Simple and practical deterministic algorithm, complicated running time

(Asked by: username_0 on 2010-11-16)

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](http://dx.doi.org/10.1007%2FBF02574703) 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.

**Tags:** ds.algorithms, soft-question, recreational
> **Comments:**
> **username_1**: 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...  
> **username_2**: 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.  
> **username_0**: @arnab: Thanks, AKS is a good idea. But I'm not sure if we can call it "practical"?  
> **username_3**: Do message-passing schemes like survey propagation, constraint propagation or sequential TRW count as "algorithms"? Easy to implement, runtime is hard to predict  
> **username_4**: 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...  
> **username_5**: Interesting that the two most popular answers involve running times that have inverse Ackermann terms. So "inverse Ackermann" is tantamount to "hard to analyze"  
> **username_0**: @Yaroslav: Everything counts (as long as it's practical and deterministic), but please note that I'm looking for something that *has* been analysed successfully, and the end result just happens to be a messy, complicated function of $n$.  

---

## 5 answers

### Answer by username_9 on 2010-11-16. Score: 20 | Accepted answer

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

> **Comments:**
> **username_0**: Excellent example, thanks! This isn't going to be easy to beat. :)  
> **username_14**: 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".)  
> **username_0**: 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!  

---

### Answer by username_6 on 2010-11-16. Score: 24

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

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

> **Comments:**
> **username_7**: 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.  
> **username_0**: 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. :)  
> **username_8**: The ratio of algorithm length to proof complexity for union-find is probably unbeatable -- all three operations are what, nine lines of code?  
> **username_9**: 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.  

---

### Answer by username_10 on 2010-11-17. Score: 6

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

> **Comments:**
> **username_0**: 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$?  
> **username_5**: 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  
> **username_10**: 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. http://gilkalai.wordpress.com/2010/11/09/subexponential-lower-bound-for-randomized-pivot-rules/  
> **username_5**: good point, Mohit. I was confused as well.  

---

### Answer by username_11 on 2010-11-18. Score: 2

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.


---

### Answer by username_12 on 2010-11-16. Score: 2

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.

> **Comments:**
> **username_0**: And what is the problem solved by this algorithm...?  
> **username_12**: It suggests looking for novel run-time analysis techniques.  
> **username_13**: 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".  

---

