<p><a href="http://en.wikipedia.org/wiki/Gr%C3%B6bner_basis">Groebner bases</a>.  The worst-case running time is doubly-exponential (in the number of variables).  In practice however, especially for well-structured problems, the <a href="http://en.wikipedia.org/wiki/Faug%C3%A8re_F4_algorithm">F4 and F5</a> algorithms are effective (i.e. terminate quite quickly).  It is still an active area of research to figure out what the proper conjecture even should be regarding the average or expected running time.  It is conjectured that it is related, somehow, to the volume of the Newton polytope of the underlying ideal.</p>

CC BY-SA 4.0
2020-10-02T16:12:35.760Z
@JacquesCarette: Curious why you say GB and DPLL are essentially equivalent? e.g. if you try to solve equations mod p, DPLL searches all p^n possible assignments, while GB does quite a bit of algebraic reasoning. Also, the polynomial calculus proof system (Clegg-Edmonds-Impagliazzo), which can essentially be implemented with GB, is provably more powerful than Resolution (which essentially corresponds to DPLL). Nonetheless, I'd believe there are other ways in which they can be seen as more equivalent, and I'd be very interested to hear about them!
Joshua Grochow
CC BY-SA 4.0
2020-10-03T18:51:22.353Z
@JoshuaGrochow I would start with this talk https://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=&ved=2ahUKEwj9ztKxiZnsAhUHZd8KHT4_AYUQFjAMegQIEBAD&url=https%3A%2F%2Fhomes.cs.washington.edu%2F~beame%2Ftalks%2Fsat05invite.ppt&usg=AOvVaw2EVQ3UEjT0ZFkWPPrPeH9J . Right now, I can't find where I learned about the relation between all these systems - sorry, this is outside of my current domain of research.
Jacques Carette
CC BY-SA 2.5
2010-08-19T13:54:40.100Z
Average/expected under what distribution?  I thought even defining the expected running time was difficult for algebraic problems...
Joshua Grochow
CC BY-SA 2.5
2010-08-19T16:27:59.717Z
I don't know for the cases solved quickly by F4 and F5 methods, but it is quite easy to build a system of polynomials with many variables and low degree which encode a SAT instance. 

In such case it is not known to me that the algorithm outperform DPLL/DPLL+.  I would really like to know more about experimental results on these things!
MassimoLauria
CC BY-SA 2.5
2010-08-20T01:01:17.163Z
@Joshua: at this point, any distribution that allows results...  @Massimo: encoding problem X as an instance of Y almost never beats specialized algorithms for X!  But GB and DPLL are essentially equivalent, so I would be extra surprised to see an effective difference.
Jacques Carette
CC BY-SA 2.5
2010-09-16T14:21:13.793Z
@Massimo: Yes, GB computation is NP-Hard. Depending on the formulation. In fact, most questions (completion, ideal membership, algebraically closed field vs booleans) are PSPACE complete or worse (EXPSPACE complete). Which is to say that GB computations are expected to be much harder than NP-complete problems (and so even avg case, any algorithm for them like F5 would most likely not outperform DPLL).
Mitch
CC BY-SA 2.5
2010-08-19T12:37:53.860Z
2010-08-19T12:37:53.860Z
Jacques Carette
<p>A great and little-recognized example of this phenomenon is <a href="https://en.wikipedia.org/wiki/Graph_isomorphism_problem" rel="nofollow noreferrer">graph isomorphism</a>.  The best known algorithm takes something like <span class="math-container">$2^{O((\log n)^3)}$</span> time, but graph isomorphism tends to be solvable quite quickly in practice.</p>
<p>I don't know if there's a formal result on average/smoothed complexity of the problem, but I remember reading that one existed - maybe someone else can chime in pointing out a formal result.  Certainly, there's a good deal of experimental evidence and a lot of fast solvers.  I'm also curious if this property extends to other members of the GI-complete family.</p>

CC BY-SA 2.5
2010-11-19T14:42:30.200Z
I don't know of any smoothed analysis for GI--or even what that would look like, exactly--but there is analysis of the best-known practical implementation (nauty) which shows that it runs in worst-case exponential time. Of course, nauty is not implementing the $O(2^{\sqrt{n \log n}})$ algorithm.  See http://cstheory.stackexchange.com/questions/3128/is-there-any-other-algorithm-whose-worst-case-running-time-is-exponential-meanwhi/3143#3143 for a reference.
Joshua Grochow
CC BY-SA 2.5
2010-11-19T14:44:36.393Z
Oh!  Maybe you're thinking of Babai-Kucera, which gives a linear-time average-case algorithm for GI: http://doi.ieeecomputersociety.org/10.1109/SFCS.1979.8
Joshua Grochow
CC BY-SA 2.5
2010-11-30T22:36:10.637Z
Yes, Babai-Kucera is the one!  Thanks for the reference.
Anand Kulkarni
CC BY-SA 4.0
2010-09-16T06:28:47.083Z
2022-11-01T07:02:34.320Z
2022-11-01T07:02:34.320Z
Anand Kulkarni
<p>Another example that has not been well understood until recently is the running time of <a href="http://en.wikipedia.org/wiki/Lloyd%27s_algorithm">Lloyd's k-means algorithm</a>, which (from a practical standpoint) has been the clustering algorithm of choice for more than 50 years. Only recently, in 2009, it has been proven (by <a href="http://arxiv.org/abs/0812.0382">Vattani</a>) that in the worst case, Lloyd's algorithm requires a number of iterations that is exponential in the number of input points. On the other hand, at the same time, a smoothed analysis (by <a href="http://arxiv.org/abs/0904.1113">Arthur, Manthey and Röglin</a>) proved that the smoothed number of iterations is merely polynomial, which explained the empirical performance.</p>

CC BY-SA 2.5
2010-08-19T15:52:02.957Z
2010-08-19T16:00:53.747Z
2010-08-19T16:00:53.747Z
MRA
<p>From David Johnson, a discrepancy in theoretical vs. experimental approximation ratios:
<a href="http://www2.research.att.com/~dsj/papers/TSPchapter.pdf">The Traveling Salesman Problem: A Case Study in Local Optimization, D. S. Johnson and L. A. McGeoch</a>.  In this paper they give experimental evidence of asymptotics (since the experiments run up to size N=10,000,000!) that defy the theoretical asymptotics: Jon Bentley's
"Greedy" or "Multi-Fragment" algorithm (worst-case approximation ratio
at least logN/loglogN) beats Nearest Insertion and Double MST, both of which have worst-case approximation ratios of 2.</p>

CC BY-SA 2.5
2010-08-19T16:00:41.313Z
2010-08-19T16:00:41.313Z
Joshua Grochow
<p>Damas-Milner type inference is proven complete for exponential time, and there are easily constructed cases with exponential blowup in the size of a result. Nonetheless, on most real-world inputs it behaves in an effectively linear fashion.</p>

CC BY-SA 2.5
2010-08-26T09:21:31.183Z
Is there a reference you would recommend for this result? I'd like to read more about it.
Radu GRIGore
CC BY-SA 2.5
2010-08-26T17:53:20.677Z
I haven't read it myself, but the most frequently cited paper is Harry G. Mairson, "Decidability of ML typing is complete for deterministic exponential time," 17th Symposium on Principles of Programming Languages (1990).
sclv
CC BY-SA 2.5
2010-08-25T17:35:35.537Z
2010-08-25T17:35:35.537Z
sclv
<p>The traversal, deque, and split corollaries of the <a href="http://en.wikipedia.org/wiki/Splay_tree#Dynamic_optimality_conjecture">dynamic optimality conjecture</a> for splay trees are examples of such gaps. Experiments back up the claim for linear time, but there is no known proof.</p>

CC BY-SA 2.5
2010-08-21T00:14:05.503Z
Seth Pettie proved that n deque operations take no more than O(n alpha*(n)) time, where "alpha*" is the iterated inverse Ackermann function, which is a pretty small gap.
jbapple
CC BY-SA 2.5
2010-08-19T12:18:03.027Z
2010-08-19T12:18:03.027Z
Radu GRIGore
<p>There is a slight issue with the question. There are in fact more than two ways of analyzing an algorithm, and one of the theoretical ways which has been neglected is expected run time, rather than worst case run time. It is really this average case behaviour that is relevant to doing experiments. Here is a very simple example: Imagine that you have an algorithm for an input of size n, which takes time n for each possible input of size n except for one specific input of each length which takes time 2^n. Hear the worst case run time is exponential, but the average case is [(2^n -1)n + (2^n)1]/(2^n) = n - (n-1)/2^n which limits to n. Clearly the two types of analysis give very different answers, but this is to be expected as we are calculating different quantities.</p>

<p>By running the experiment a bunch of times, even if we take the longest run time for the sample, we are still only sampling a small portion of the space of possible inputs, and so if hard instances are rare then we are likely to miss them.</p>

<p>It is relatively easy to construct such a problem: If the first n/2 bits are all zero, than solve the 3SAT instance encoded with the last n/2 bits. Otherwise reject. As n gets large the problem has roughly the same run time in the worst case as the most efficient algorithm for 3SAT, where as the average run time is guaranteed to be very low.</p>

CC BY-SA 2.5
2010-08-19T15:42:22.257Z
I already replied to James King above that I'm expecting most interesting answers will be about expected runtime. I'll edit the question to make this more visible.
Radu GRIGore
CC BY-SA 2.5
2010-08-19T15:38:43.987Z
2010-08-19T15:38:43.987Z
Joe Fitzsimons
<p>The PTAS for Steiner tree in planar graphs has a ridiculous dependence on epsilon. However there is <a href="http://www.siam.org/proceedings/alenex/2009/alx09_012_tazaris.pdf">an implementation</a> that shows a surprisingly good performance in practice.</p>

CC BY-SA 2.5
2010-09-18T03:21:18.567Z
2010-09-18T03:21:18.567Z
zotachidil
<p>Pairing heaps, from [1] - they implement heaps, where insert and merge have O(log n) amortized complexity, but are conjectured to be O(1). In practice, they are extremely efficient, especially for users of merge.</p>

<p>I just discovered them just today while reading Sec. 5.5 of C. Okasaki's book "Purely functional data structures", so I thought I should share info about them.</p>

<p>[1] Fredman, M. L., Sedgewick, R., Sleator, D. D., and Tarjan, R. E. 1986. The pairing heap: a new form of self-adjusting heap. Algorithmica 1, 1 (Jan. 1986), 111-129. DOI= <a href="http://dx.doi.org/10.1007/BF01840439">http://dx.doi.org/10.1007/BF01840439</a> </p>

CC BY-SA 2.5
2010-10-24T14:28:50.600Z
There have been some advancements since Okasaki, and there are now (imperative) pairing heaps with O(0) meld, O(1) insert and findMin, O(lg lg n) decreaseKey, and O(lg n) deleteMin: http://arxiv.org/abs/0903.4130 . This heap uses a different pairing mechanism than the original pairing heaps of Fredman et al.
jbapple
CC BY-SA 2.5
2010-09-09T03:48:15.207Z
2010-09-09T03:48:15.207Z
Blaisorblade
<p>The Lin-Kernighan heuristic for the TSP ("An effective heuristic for the traveling salesman problem", Operations Research 21:489–516, 1973) is very successful in practice, but still lacks an average-case or smoothed analysis to explain its performance. It contrast, there is a smoothed analysis of the 2-opt heuristic for the TSP by Matthias Englert, Heiko Röglin, and Berthold Vöcking (Algorithmica, to appear).</p>

CC BY-SA 3.0
2013-10-15T18:13:14.837Z
2013-10-17T11:20:17.443Z
2013-10-17T11:20:17.443Z
Bodo Manthey
<p>There are many very fast and efficient in practice <a href="http://en.wikipedia.org/wiki/Branch_and_bound" rel="nofollow">branch and bound</a> algorithms for different NP-hard problems that we can not rigorously analyze: TSP, Steiner tree, bin packing and so on.</p>

<p>Also there are very nice algorithms for max-flow that are in practice almost linear, but only $\Omega(nm)$ bounds are proven for them.</p>

CC BY-SA 2.5
2010-08-26T09:21:56.800Z
You mean O(mn), or am I confused?
Radu GRIGore
CC BY-SA 2.5
2010-08-26T16:13:41.133Z
The best bound so far is $O(nm log (n^2 / m))$.
ilyaraz
CC BY-SA 2.5
2010-08-20T17:41:57.820Z
2010-08-21T02:01:45.850Z
2010-08-21T02:01:45.850Z
ilyaraz
<p>The most glaring example is of course the Simplex method that runs quickly in practice, suggesting poly-timeness, but takes exponential time in theory.  Dan Spielman just got the Nevanlinna award to a large extent for explaining this mystery.</p>

<p>More generally, many instances of Integer-programming can be solved quite well using standard IP-solvers, e.g. combinatorial auctions for most distributions attempted on significant sized inputs could be solved -- <a href="http://www.cis.upenn.edu/~mkearns/teaching/cgt/combinatorial-auctions-survey.pdf">http://www.cis.upenn.edu/~mkearns/teaching/cgt/combinatorial-auctions-survey.pdf</a></p>

CC BY-SA 3.0
2013-10-17T23:42:25.167Z
there are lowerbounds for some specific pivoting rule in this paper http://cs.au.dk/~tdh/papers/random_edge.pdf
Igor Shinkar
CC BY-SA 2.5
2010-08-19T14:58:35.843Z
Has there been an explicit family of linear programs found for which simplex takes exponential time?
Opt
CC BY-SA 2.5
2010-08-19T15:33:57.510Z
As far as I understand, there are many explicit families that require exponential time (e.g., the first beeing given by Klee and Minty: "How good is the simplex algorithm?", 1972). However, the choice of the pivot rule is relevant for these results. I guess most of the references to these results can be found in Spielman and Teng's paper (http://arxiv.org/abs/cs/0111050).
MRA
CC BY-SA 2.5
2010-08-19T14:51:49.340Z
2010-08-19T15:14:22.290Z
2010-08-19T15:14:22.290Z
Noam
<p>Two ways of analyzing the efficiency of an algorithm are</p>

<ol>
<li>to put an asymptotic upper bound on its runtime, and</li>
<li>to run it and collect experimental data.</li>
</ol>

<p>I wonder if there are known cases where there is a <em>significant</em> gap between (1) and (2). By this I mean that either (a) the experimental data suggests a tighter asymptotic or (b) there are algorithms X and Y such that the theoretical analysis suggests that X is much better than Y and the experimental data suggests that Y is much better than X.</p>

<p>Since experiments usually reveal average-case behavior, I expect most interesting answers to refer to average-case upper bounds. However, I don't want to rule out possibly interesting answers that talk about different bounds, such as Noam's answer about Simplex.</p>

<p>Include data structures. Please put one algo/ds per answer.</p>

CC BY-SA 2.5
2010-08-19T14:46:23.893Z
It would help if you clarified what kind of upper bounds you're talking about.  Are you only talking about problems for which there is a significant gap between best known upper and lower bounds for worst-case time complexity?  Or are you also including problems for which tight bounds on the worst-case time complexity are known, but typical running times are significantly faster?  It may be more interesting to consider smoothed complexity rather than worst-case complexity.  Experimental results on 'typical' inputs or random inputs do little to disprove the existence of pathological inputs.
James King
CC BY-SA 2.5
2010-08-19T16:01:18.100Z
In that case I think there are two questions that should be asked separately: one about gaps between worst-case complexity and average-case/smoothed complexity, and one about gaps between theoretical average-case/smoothed complexity and practical experimental results.

Edit: you made an edit addressing this while I was writing my comment :)
James King
<ds.algorithms><big-list><ds.data-structures>
For which algorithms is there a large gap between the theoretical analysis and reality?
Radu GRIGore
# For which algorithms is there a large gap between the theoretical analysis and reality?

(Asked by: username_0 on 2010-08-19)

Two ways of analyzing the efficiency of an algorithm are

1. to put an asymptotic upper bound on its runtime, and
2. to run it and collect experimental data.

I wonder if there are known cases where there is a *significant* gap between (1) and (2). By this I mean that either (a) the experimental data suggests a tighter asymptotic or (b) there are algorithms X and Y such that the theoretical analysis suggests that X is much better than Y and the experimental data suggests that Y is much better than X.

Since experiments usually reveal average-case behavior, I expect most interesting answers to refer to average-case upper bounds. However, I don't want to rule out possibly interesting answers that talk about different bounds, such as Noam's answer about Simplex.

Include data structures. Please put one algo/ds per answer.

**Tags:** ds.algorithms, big-list, ds.data-structures
> **Comments:**
> **username_1**: It would help if you clarified what kind of upper bounds you're talking about.  Are you only talking about problems for which there is a significant gap between best known upper and lower bounds for worst-case time complexity?  Or are you also including problems for which tight bounds on the worst-case time complexity are known, but typical running times are significantly faster?  It may be more interesting to consider smoothed complexity rather than worst-case complexity.  Experimental results on 'typical' inputs or random inputs do little to disprove the existence of pathological inputs.  
> **username_1**: In that case I think there are two questions that should be asked separately: one about gaps between worst-case complexity and average-case/smoothed complexity, and one about gaps between theoretical average-case/smoothed complexity and practical experimental results.  Edit: you made an edit addressing this while I was writing my comment :)  

---

## 12 answers

### Answer by username_15 on 2010-08-19. Score: 44 | Accepted answer

The most glaring example is of course the Simplex method that runs quickly in practice, suggesting poly-timeness, but takes exponential time in theory. Dan Spielman just got the Nevanlinna award to a large extent for explaining this mystery.

More generally, many instances of Integer-programming can be solved quite well using standard IP-solvers, e.g. combinatorial auctions for most distributions attempted on significant sized inputs could be solved -- <http://www.cis.upenn.edu/~mkearns/teaching/cgt/combinatorial-auctions-survey.pdf>

> **Comments:**
> **username_17**: Has there been an explicit family of linear programs found for which simplex takes exponential time?  
> **username_7**: As far as I understand, there are many explicit families that require exponential time (e.g., the first beeing given by Klee and Minty: "How good is the simplex algorithm?", 1972). However, the choice of the pivot rule is relevant for these results. I guess most of the references to these results can be found in Spielman and Teng's paper (http://arxiv.org/abs/cs/0111050).  
> **username_16**: there are lowerbounds for some specific pivoting rule in this paper http://cs.au.dk/~tdh/papers/random_edge.pdf  

---

### Answer by username_2 on 2010-08-19. Score: 30

[Groebner bases](http://en.wikipedia.org/wiki/Gr%C3%B6bner_basis). The worst-case running time is doubly-exponential (in the number of variables). In practice however, especially for well-structured problems, the [F4 and F5](http://en.wikipedia.org/wiki/Faug%C3%A8re_F4_algorithm) algorithms are effective (i.e. terminate quite quickly). It is still an active area of research to figure out what the proper conjecture even should be regarding the average or expected running time. It is conjectured that it is related, somehow, to the volume of the Newton polytope of the underlying ideal.

> **Comments:**
> **username_3**: Average/expected under what distribution?  I thought even defining the expected running time was difficult for algebraic problems...  
> **username_4**: I don't know for the cases solved quickly by F4 and F5 methods, but it is quite easy to build a system of polynomials with many variables and low degree which encode a SAT instance.   In such case it is not known to me that the algorithm outperform DPLL/DPLL+.  I would really like to know more about experimental results on these things!  
> **username_2**: @Joshua: at this point, any distribution that allows results...  @Massimo: encoding problem X as an instance of Y almost never beats specialized algorithms for X!  But GB and DPLL are essentially equivalent, so I would be extra surprised to see an effective difference.  
> **username_5**: @Massimo: Yes, GB computation is NP-Hard. Depending on the formulation. In fact, most questions (completion, ideal membership, algebraically closed field vs booleans) are PSPACE complete or worse (EXPSPACE complete). Which is to say that GB computations are expected to be much harder than NP-complete problems (and so even avg case, any algorithm for them like F5 would most likely not outperform DPLL).  
> **username_3**: @JacquesCarette: Curious why you say GB and DPLL are essentially equivalent? e.g. if you try to solve equations mod p, DPLL searches all p^n possible assignments, while GB does quite a bit of algebraic reasoning. Also, the polynomial calculus proof system (Clegg-Edmonds-Impagliazzo), which can essentially be implemented with GB, is provably more powerful than Resolution (which essentially corresponds to DPLL). Nonetheless, I'd believe there are other ways in which they can be seen as more equivalent, and I'd be very interested to hear about them!  
> **username_2**: @JoshuaGrochow I would start with this talk https://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=&ved=2ahUKEwj9ztKxiZnsAhUHZd8KHT4_AYUQFjAMegQIEBAD&url=https%3A%2F%2Fhomes.cs.washington.edu%2F~beame%2Ftalks%2Fsat05invite.ppt&usg=AOvVaw2EVQ3UEjT0ZFkWPPrPeH9J . Right now, I can't find where I learned about the relation between all these systems - sorry, this is outside of my current domain of research.  

---

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

A great and little-recognized example of this phenomenon is [graph isomorphism](https://en.wikipedia.org/wiki/Graph_isomorphism_problem). The best known algorithm takes something like $2^{O((\log n)^3)}$ time, but graph isomorphism tends to be solvable quite quickly in practice.

I don't know if there's a formal result on average/smoothed complexity of the problem, but I remember reading that one existed - maybe someone else can chime in pointing out a formal result. Certainly, there's a good deal of experimental evidence and a lot of fast solvers. I'm also curious if this property extends to other members of the GI-complete family.

> **Comments:**
> **username_3**: I don't know of any smoothed analysis for GI--or even what that would look like, exactly--but there is analysis of the best-known practical implementation (nauty) which shows that it runs in worst-case exponential time. Of course, nauty is not implementing the $O(2^{\sqrt{n \log n}})$ algorithm.  See http://cstheory.stackexchange.com/questions/3128/is-there-any-other-algorithm-whose-worst-case-running-time-is-exponential-meanwhi/3143#3143 for a reference.  
> **username_3**: Oh!  Maybe you're thinking of Babai-Kucera, which gives a linear-time average-case algorithm for GI: http://doi.ieeecomputersociety.org/10.1109/SFCS.1979.8  
> **username_6**: Yes, Babai-Kucera is the one!  Thanks for the reference.  

---

### Answer by username_7 on 2010-08-19. Score: 22

Another example that has not been well understood until recently is the running time of [Lloyd's k-means algorithm](http://en.wikipedia.org/wiki/Lloyd%27s_algorithm), which (from a practical standpoint) has been the clustering algorithm of choice for more than 50 years. Only recently, in 2009, it has been proven (by [Vattani](http://arxiv.org/abs/0812.0382)) that in the worst case, Lloyd's algorithm requires a number of iterations that is exponential in the number of input points. On the other hand, at the same time, a smoothed analysis (by [Arthur, Manthey and Röglin](http://arxiv.org/abs/0904.1113)) proved that the smoothed number of iterations is merely polynomial, which explained the empirical performance.


---

### Answer by username_3 on 2010-08-19. Score: 21

From David Johnson, a discrepancy in theoretical vs. experimental approximation ratios:
[The Traveling Salesman Problem: A Case Study in Local Optimization, D. S. Johnson and L. A. McGeoch](http://www2.research.att.com/~dsj/papers/TSPchapter.pdf). In this paper they give experimental evidence of asymptotics (since the experiments run up to size N=10,000,000!) that defy the theoretical asymptotics: Jon Bentley's
"Greedy" or "Multi-Fragment" algorithm (worst-case approximation ratio
at least logN/loglogN) beats Nearest Insertion and Double MST, both of which have worst-case approximation ratios of 2.


---

### Answer by username_8 on 2010-08-25. Score: 11

Damas-Milner type inference is proven complete for exponential time, and there are easily constructed cases with exponential blowup in the size of a result. Nonetheless, on most real-world inputs it behaves in an effectively linear fashion.

> **Comments:**
> **username_0**: Is there a reference you would recommend for this result? I'd like to read more about it.  
> **username_8**: I haven't read it myself, but the most frequently cited paper is Harry G. Mairson, "Decidability of ML typing is complete for deterministic exponential time," 17th Symposium on Principles of Programming Languages (1990).  

---

### Answer by username_0 on 2010-08-19. Score: 11

The traversal, deque, and split corollaries of the [dynamic optimality conjecture](http://en.wikipedia.org/wiki/Splay_tree#Dynamic_optimality_conjecture) for splay trees are examples of such gaps. Experiments back up the claim for linear time, but there is no known proof.

> **Comments:**
> **username_9**: Seth Pettie proved that n deque operations take no more than O(n alpha*(n)) time, where "alpha*" is the iterated inverse Ackermann function, which is a pretty small gap.  

---

### Answer by username_10 on 2010-08-19. Score: 10

There is a slight issue with the question. There are in fact more than two ways of analyzing an algorithm, and one of the theoretical ways which has been neglected is expected run time, rather than worst case run time. It is really this average case behaviour that is relevant to doing experiments. Here is a very simple example: Imagine that you have an algorithm for an input of size n, which takes time n for each possible input of size n except for one specific input of each length which takes time 2^n. Hear the worst case run time is exponential, but the average case is [(2^n -1)n + (2^n)1]/(2^n) = n - (n-1)/2^n which limits to n. Clearly the two types of analysis give very different answers, but this is to be expected as we are calculating different quantities.

By running the experiment a bunch of times, even if we take the longest run time for the sample, we are still only sampling a small portion of the space of possible inputs, and so if hard instances are rare then we are likely to miss them.

It is relatively easy to construct such a problem: If the first n/2 bits are all zero, than solve the 3SAT instance encoded with the last n/2 bits. Otherwise reject. As n gets large the problem has roughly the same run time in the worst case as the most efficient algorithm for 3SAT, where as the average run time is guaranteed to be very low.

> **Comments:**
> **username_0**: I already replied to James King above that I'm expecting most interesting answers will be about expected runtime. I'll edit the question to make this more visible.  

---

### Answer by username_11 on 2010-09-18. Score: 9

The PTAS for Steiner tree in planar graphs has a ridiculous dependence on epsilon. However there is [an implementation](http://www.siam.org/proceedings/alenex/2009/alx09_012_tazaris.pdf) that shows a surprisingly good performance in practice.


---

### Answer by username_12 on 2010-09-09. Score: 8

Pairing heaps, from [1] - they implement heaps, where insert and merge have O(log n) amortized complexity, but are conjectured to be O(1). In practice, they are extremely efficient, especially for users of merge.

I just discovered them just today while reading Sec. 5.5 of C. Okasaki's book "Purely functional data structures", so I thought I should share info about them.

[1] Fredman, M. L., Sedgewick, R., Sleator, D. D., and Tarjan, R. E. 1986. The pairing heap: a new form of self-adjusting heap. Algorithmica 1, 1 (Jan. 1986), 111-129. DOI= <http://dx.doi.org/10.1007/BF01840439>

> **Comments:**
> **username_9**: There have been some advancements since Okasaki, and there are now (imperative) pairing heaps with O(0) meld, O(1) insert and findMin, O(lg lg n) decreaseKey, and O(lg n) deleteMin: http://arxiv.org/abs/0903.4130 . This heap uses a different pairing mechanism than the original pairing heaps of Fredman et al.  

---

### Answer by username_13 on 2013-10-15. Score: 8

The Lin-Kernighan heuristic for the TSP ("An effective heuristic for the traveling salesman problem", Operations Research 21:489–516, 1973) is very successful in practice, but still lacks an average-case or smoothed analysis to explain its performance. It contrast, there is a smoothed analysis of the 2-opt heuristic for the TSP by Matthias Englert, Heiko Röglin, and Berthold Vöcking (Algorithmica, to appear).


---

### Answer by username_14 on 2010-08-20. Score: 5

There are many very fast and efficient in practice [branch and bound](http://en.wikipedia.org/wiki/Branch_and_bound) algorithms for different NP-hard problems that we can not rigorously analyze: TSP, Steiner tree, bin packing and so on.

Also there are very nice algorithms for max-flow that are in practice almost linear, but only $\Omega(nm)$ bounds are proven for them.

> **Comments:**
> **username_0**: You mean O(mn), or am I confused?  
> **username_14**: The best bound so far is $O(nm log (n^2 / m))$.  

---

