59
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – James King
    Commented Aug 19, 2010 at 14:46
  • $\begingroup$ 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 :) $\endgroup$
    – James King
    Commented Aug 19, 2010 at 16:01

13 Answers 13

Reset to default
44
$\begingroup$

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

Improve this answer
$\endgroup$
4
  • 4
    $\begingroup$ Has there been an explicit family of linear programs found for which simplex takes exponential time? $\endgroup$
    – Opt
    Commented Aug 19, 2010 at 14:58
  • 2
    $\begingroup$ 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). $\endgroup$
    – MRA
    Commented Aug 19, 2010 at 15:33
  • 2
    $\begingroup$ @Sid: Yes. the Klee-Minty cube: glossary.computing.society.informs.org/notes/Klee-Minty.pdf $\endgroup$
    – user232
    Commented Aug 19, 2010 at 15:36
  • $\begingroup$ there are lowerbounds for some specific pivoting rule in this paper cs.au.dk/~tdh/papers/random_edge.pdf $\endgroup$
    – Igor Shinkar
    Commented Oct 17, 2013 at 23:42
30
$\begingroup$

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.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Average/expected under what distribution? I thought even defining the expected running time was difficult for algebraic problems... $\endgroup$
    – Joshua Grochow
    Commented Aug 19, 2010 at 13:54
  • 1
    $\begingroup$ 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! $\endgroup$
    – MassimoLauria
    Commented Aug 19, 2010 at 16:27
  • $\begingroup$ @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. $\endgroup$
    – Jacques Carette
    Commented Aug 20, 2010 at 1:01
  • 2
    $\begingroup$ @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). $\endgroup$
    – Mitch
    Commented Sep 16, 2010 at 14:21
  • $\begingroup$ @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! $\endgroup$
    – Joshua Grochow
    Commented Oct 2, 2020 at 16:12
24
$\begingroup$

A great and little-recognized example of this phenomenon is graph isomorphism. 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.

Improve this answer
$\endgroup$
3
  • 2
    $\begingroup$ 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. $\endgroup$
    – Joshua Grochow
    Commented Nov 19, 2010 at 14:42
  • 3
    $\begingroup$ 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 $\endgroup$
    – Joshua Grochow
    Commented Nov 19, 2010 at 14:44
  • $\begingroup$ Yes, Babai-Kucera is the one! Thanks for the reference. $\endgroup$
    – Anand Kulkarni
    Commented Nov 30, 2010 at 22:36
22
$\begingroup$

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.

Improve this answer
$\endgroup$
21
$\begingroup$

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.

Improve this answer
$\endgroup$
11
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 5
    $\begingroup$ 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. $\endgroup$
    – jbapple
    Commented Aug 21, 2010 at 0:14
11
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Is there a reference you would recommend for this result? I'd like to read more about it. $\endgroup$
    – Radu GRIGore
    Commented Aug 26, 2010 at 9:21
  • 1
    $\begingroup$ 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). $\endgroup$
    – sclv
    Commented Aug 26, 2010 at 17:53
10
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Radu GRIGore
    Commented Aug 19, 2010 at 15:42
9
$\begingroup$

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.

Improve this answer
$\endgroup$
8
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – jbapple
    Commented Oct 24, 2010 at 14:28
8
$\begingroup$

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

Improve this answer
$\endgroup$
7
$\begingroup$

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.

Improve this answer
$\endgroup$
5
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ You mean O(mn), or am I confused? $\endgroup$
    – Radu GRIGore
    Commented Aug 26, 2010 at 9:21
  • $\begingroup$ The best bound so far is $O(nm log (n^2 / m))$. $\endgroup$
    – ilyaraz
    Commented Aug 26, 2010 at 16:13

Not the answer you're looking for? Browse other questions tagged or ask your own question.