# For which algorithms is there a large gap between the theoretical analysis and reality?

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.

• 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. Aug 19 '10 at 14:46
• 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 :) Aug 19 '10 at 16:01

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

• Has there been an explicit family of linear programs found for which simplex takes exponential time?
– Opt
Aug 19 '10 at 14:58
• 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 (arxiv.org/abs/cs/0111050).
– MRA
Aug 19 '10 at 15:33
• @Sid: Yes. the Klee-Minty cube: glossary.computing.society.informs.org/notes/Klee-Minty.pdf
– user232
Aug 19 '10 at 15:36
• there are lowerbounds for some specific pivoting rule in this paper cs.au.dk/~tdh/papers/random_edge.pdf Oct 17 '13 at 23:42

Groebner bases. 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 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.

• Average/expected under what distribution? I thought even defining the expected running time was difficult for algebraic problems... Aug 19 '10 at 13:54
• 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! Aug 19 '10 at 16:27
• @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. Aug 20 '10 at 1:01
• @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). Sep 16 '10 at 14:21
• @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! Oct 2 '20 at 16:12

A great and little-recognized example of this phenomenon is graph isomorphism. The best known algorithm takes something like $O(2^{(\sqrt{(n log n)})})$ 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.

• 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 cstheory.stackexchange.com/questions/3128/… for a reference. Nov 19 '10 at 14:42
• Oh! Maybe you're thinking of Babai-Kucera, which gives a linear-time average-case algorithm for GI: doi.ieeecomputersociety.org/10.1109/SFCS.1979.8 Nov 19 '10 at 14:44
• Yes, Babai-Kucera is the one! Thanks for the reference. Nov 30 '10 at 22:36

Another example that has not been well understood until recently is the running time of Lloyd's k-means 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) 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) proved that the smoothed number of iterations is merely polynomial, which explained the empirical performance.

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

The traversal, deque, and split corollaries of the 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.

• 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. Aug 21 '10 at 0:14

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.

• Is there a reference you would recommend for this result? I'd like to read more about it. Aug 26 '10 at 9:21
• 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
Aug 26 '10 at 17:53

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.

• 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. Aug 19 '10 at 15:42

The PTAS for Steiner tree in planar graphs has a ridiculous dependence on epsilon. However there is an implementation that shows a surprisingly good performance in practice.

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

• 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: arxiv.org/abs/0903.4130 . This heap uses a different pairing mechanism than the original pairing heaps of Fredman et al. Oct 24 '10 at 14:28

Related to ilyaraz's remark about branch and bound, Pataki et al. show that branch and bound plus lattice basis reduction can solve almost all random IP's in polytime.

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

There are many very fast and efficient in practice 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.

• You mean O(mn), or am I confused? Aug 26 '10 at 9:21
• The best bound so far is $O(nm log (n^2 / m))$. Aug 26 '10 at 16:13