Take the 2-minute tour ×

Is there a widely-used algorithm that has time complexity worse than that of another known algorithm but it is a better choice in all practical situations (worse complexity but better otherwise)?

An acceptable answer might be in a form:

There are algorithms A and B that have O(N**2) and O(N) time complexity correspondingly, but B has such a big constant that it has no advantages over A for inputs less then a number of atoms in the Universe.

Examples highlights from the answers:

  • Simplex algorithm -- worst-case is exponential time -- vs. known polynomial-time algorithms for convex optimization problems.

  • A naive median of medians algorithm -- worst-case O(N**2) vs. known O(N) algorithm.

  • Backtracking regex engines -- worst-case exponential vs. O(N) Thompson NFA -based engines.

All these examples exploit worst-case vs. average scenarios.

Are there examples that do not rely on the difference between the worst case vs. average case scenario?


  • The Rise of ``Worse is Better''. (For the purpose of this question the "Worse is Better" phrase is used in a narrower (namely -- algorithmic time-complexity) sense than in the article)

  • Python's Design Philosophy:


    This example would be the answer if there were no computers capable of storing these large collections (in other words large is not large enough in this case).

  • Coppersmith–Winograd algorithm for square matrix multiplication is a good example (it is the fastest (2008) but it is inferior to worse algorithms). Any others? From the wikipedia article: "It is not used in practice because it only provides an advantage for matrices so large that they cannot be processed by modern hardware (Robinson 2005)."

share|improve this question
In what way is Coppersmith-Winograd "inferior" to "worse" algorithms? By itself, the statement is contradictory; some more explanation would be great, and might help others understand exactly what your question is. –  Matt J Jan 23 '09 at 17:40
I've fixed Coppersmith-Windograd algorithm's link (the markup doesn't like some dashes). –  J.F. Sebastian Jan 23 '09 at 18:07
@Math J: I've added clarification on why Coppersmith-Winograd algorithm is inferior. –  J.F. Sebastian Jan 23 '09 at 18:14
One of the possible reasons for worse to be better is if it requires less memory (if that difference is huge). I cannot think of a real example, so I'm just posting this as comment instead of answer. –  Milan Babuškov Jun 8 '09 at 8:18
You keep adding the qualifier "better in all situations" which means, I think, that you've missed the entire point of "Worse is Better". –  JUST MY correct OPINION May 31 '10 at 4:09

23 Answers 23

quick-sort has worst case time complexity of O(N^2) but it is usually considered better than other sorting algorithms which have O(N log n) time complexity in the worst case.

share|improve this answer
This is a good example but naive (unmodified) quicksort version that has O(N**2) time complexity is not widely used. –  J.F. Sebastian Jan 23 '09 at 1:53
"if the algorithm selects pivot elements uniformly at random, it has a provably high probability of finishing in O(n log n) time regardless of the characteristics of the input." en.wikipedia.org/wiki/Randomized_algorithm#Quicksort –  J.F. Sebastian Jan 23 '09 at 2:08
As I said, high probability does not affect worst case analysis. –  shoosh Jan 23 '09 at 19:07
Therefore a not naive QuickSort is a worst-case O(n*log(n)). Though I don't know whether the above selection algorithm is actually used to implement QuickSort. –  J.F. Sebastian Jan 29 '09 at 3:29
@J.F. Sebastian In Java (until Java 6), Arrays.sort for all primitive array types is implemented using a "tuned quicksort" using a pseudomedian of 9, which still has O(N^2) worst case time complexity. –  Christian Semrau Dec 13 '10 at 22:32

Simplex is an algorithm which has exponential time complexity in the worst case but for any real case it is polynomial. Probably polynomial algorithms for linear programming exist but they are very complicated and usually have large constants.

share|improve this answer
"The current opinion is that the efficiency of good implementations of simplex-based methods and interior point methods is similar for routine applications of linear programming." (from wikipedia). So Simplex's polynomial time alternatives may be more complex but they are as efficient in practice. –  J.F. Sebastian Jan 23 '09 at 18:41
One of the major advantages to RSM is that it can be hot-started after minor changes to the problem - which is exactly what you need when doing branch-and-bound for integer programming. Interior point methods are not so useful in those cases. –  Peter Jan 29 '09 at 3:23

"Worse is Better" can be seen in languages too, for example the ideas behind Perl, Python, Ruby, Php even C# or Java, or whatever language that isn't assembler or C (C++ might fit here or not).

Basically there is always a "perfect" solution, but many times its better to use a "worse" tool/algorithm/language to get results faster, and with less pain. Thats why people use these higher level languages, although they are "worse" from the ideal computer-language point of view, and instead are more human oriented.

share|improve this answer
Though it is related but it is not an answer to my question. The question is about algorithms and their time complexities. –  J.F. Sebastian Jan 23 '09 at 2:18
yeah, its not directly related to your question, but since the title doesn't limit the question to algorithms, I don't want someone new to the concept to stumble by here later on, and think that "worse is better" only applies to algorithms, when its a more general idea. –  Robert Gould Jan 23 '09 at 2:44
Technically you are correct (it is the best kind of "correct"). The title doesn't limit the scope, but the first sentence of my question does. –  J.F. Sebastian Jan 14 '11 at 12:51

Monte Carlo integration is a probabilistic method of calculating definite integrals that has no guarantee of returning the correct answer. Yet, in real-world situations it returns an accurate answer far faster than provably correct methods.

share|improve this answer
It may depends on the kind of integration region or function but It is the first time I hear that algorithm based on Monte Carlo method has no guarantee to converge. –  J.F. Sebastian Jan 23 '09 at 18:35
I was going to suggest the possibility of picking the same sample point every iteration, but reviewing the algorithm I see that is not possible. I retract the suggestion it does not converge. –  Dour High Arch Jan 23 '09 at 18:50
one might say worse is better, as it takes much longer to get to more accuracy, but the error in the answer decreases –  simonjpascoe Jan 29 '09 at 5:00
up vote 11 down vote accepted

Coppersmith–Winograd algorithm for square matrix multiplication. Its time complexity is O(n2.376) vs. O(n3) of a naive multiplication algorithm or vs. O(n2.807) for Strassen algorithm.

From the wikipedia article:

However, unlike the Strassen algorithm, it is not used in practice because it only provides an advantage for matrices so large that they cannot be processed by modern hardware (Robinson 2005).

share|improve this answer

Often an algorithm (like quicksort) that can be easily parallelized or randomized will be chosen over competing algorithms that lack these qualities. Furthermore, it is often the case that an approximate solution to a problem is acceptable when an exact algorithm would yield exponential runtimes as in the Travelling Salesman Problem.

share|improve this answer
But parallelized or randomized quicksort has different time complexities. My question is about algorithms that have worse time complexity compared to other known algorithms. –  J.F. Sebastian Jan 23 '09 at 2:05

This statement can be applied to nearly any parallel algorithm. The reason they were not heavily researched in the early days of computing is because, for a single thread of execution (think uniprocessor), they are indeed slower than their well-known sequential counterparts in terms of asymptotic complexity, constant factors for small n, or both. However, in the context of current and future computing platforms, an algorithm which can make use of a few (think multicore), few hundred (think GPU), or few thousand (think supercomputer) processing elements will beat the pants of the sequential version in wall-clock time, even if the total time/energy spent by all processors is much greater for the parallel version.

Sorts, graph algorithms, and linear algebra techniques alike can be accelerated in terms of wall-clock time by bearing the cost of a little extra bookkeeping, communication, and runtime overhead in order to parallelize.

share|improve this answer
It is a matter of definition (how to define time complexity) but I would say that parallel algorithms you are talking simply can have a better time complexity, but my question is about algorithms that have worse time complexity but nonetheless are better in all practical applications. –  J.F. Sebastian Jan 23 '09 at 2:25


Presumably the size of the collection was 641K.

When working in the technical computing group for BAE SYSTEMS, which looked after structural and aerodynamic code for various aircraft, we had a codebase going back at least 25 years (and a third of the staff had been there that long).

Many of the algorithms were optimised for performance on a 16bit mainframe, rather than for scalability. These optimisations were entirely appropriate for 1970s hardware, but performed poorly on larger datasets on the 32 and 64 bit systems which replaced it. If you're choosing something with worse scalability which works better on the hardware you are currently working on, be aware that this is an optimisation, and it may not apply in the future. At the time those 1970s routines were written, data size we put into them in the 2000s was not practical. Unfortunately, trying to extract a clear algorithm from those codes which then could be implemented to suit modern hardware was not trivial.

Short of boiling the oceans, what counts as 'all practical situations' is often a time dependent variable.

share|improve this answer
I would add: Never underestimate a source code longevity. –  J.F. Sebastian Jan 28 '09 at 12:18
Right. This was not understood in the 1960s and 1970s, because there was practically no source code decades old and still in use. –  David Thornley Jan 29 '09 at 20:19

Ok, consider solving the traveling sales man problem. The ONLY perfect solution is to test all possible routes. However that becomes impossible with our hardware and time-limits as N increases. So we have thought of many of heuristics.

Which brings us to the answer of your question. Heuristics (worse) are better than brute-force for NP-complete problems. This describes the situation in which "Worse is Better" is always true.

share|improve this answer
My question implies that "worse" means a "worse time-complexity". In your example "worse" means "a possibly incorrect" solution (good-enough vs. no solution at all for large problem sizes). –  J.F. Sebastian Jan 29 '09 at 4:27
Indeed put that way we are talking about a different "worse" –  Robert Gould Jan 29 '09 at 6:54
Traveling salesman can be solved in O(n^2 2^n) time, which is really slow, but still much faster than trying every path, which is O((n-1)!). –  Derek Ledbetter Jan 29 '09 at 8:31
Derek is right. And it has not been /proven/ that O(n^2 * 2^n) is the best perfect solution either. –  Matthew Flaschen May 22 '09 at 10:52

Radix sort has time-complexity O(n) for fixed-length inputs, but quicksort is more often used, despite the worse asympotic runtime, because the per-element overhead on Radix sort is typically much higher.

share|improve this answer
I would say Radix sort just has narrower application domain than Quick sort. –  J.F. Sebastian Jan 24 '09 at 0:45
Radix sort also places more restrictions on the elements to sort than a simple comparison operation. –  user21714 Jan 29 '09 at 4:52
Radix is only applicable in some cases. I also once implemented a hybrid radix/quicksort to deal with a lack of memory--when there isn't enough memory to hold everything radix is a lot better. –  Loren Pechtel Jan 29 '09 at 5:22

If I understand the question, you are asking for algorithms that are theoretically better but practically worse in all situations. Therefore, one would not expect them to actually be used unless by mistake.

One possible example is universal memoization. Theoretically, all deterministic function calls should be memoized for all possible inputs. That way complex calculations could be replaced by simple table lookups. For a wide range of problems, this technique productively trades time for storage space. But suppose there were a central repository of the results of all possible inputs for all possible functions used by all of humanity's computers. The first time anyone anywhere did a calculation it would be the last time. All subsequent tries would result in a table lookup.

But there are several reasons I can think of for not doing this:

  1. The memory space required to store all results would likely be impossibly large. It seems likely the number of needed bits would exceed the number of particles in the universe. (But even the task of estimating that number is daunting.)

  2. It would be difficult to construct an efficient algorithm for doing the memoiztion of that huge a problem space.

  3. The cost of communication with the central repository would likely exceed the benefit as the number of clients increase.

I'm sure you can think of other problems.

In fact, this sort of time/space trade-off is incredible common in practice. Ideally, all data would be stored in L1 cache, but because of size limitations you always need to put some data on disk or (horrors!) tape. Advancing technology reduces some of the pain of these trade-offs, but as I suggested above there are limits.

In response to J.F. Sebastian's comment:

Suppose that instead of a universal memoization repository, we consider a factorial repository. And it won't hold the results for all possible inputs. Rather it will be limited to results from 1 to N! Now it's easy to see that any computer that did factorials would benefit from looking up the result rather than doing the calculation. Even for calculating (N+1)! the lookup would be a huge win since that calculation would reduce to N!(N+1).

Now to make this "better" algorithm worse, we could either increase N or increase the number of computers using the repository.

But I'm probably not understanding some subtlety of the question. They way I'm thinking of it, I keep coming up with examples that scale well until they don't.

share|improve this answer
You are correct about meaning of my answer. But you are wrong about universal repository even theoretically. There is a theorem that states that it is impossible to enumerate all possible results of all possible inputs for all possible functions even if we would have an infinite resources. –  J.F. Sebastian Jan 29 '09 at 22:25
You are assuming that lookup is O(1) operation but it is not for sufficiently large N. Therefore its time-complexity is not always superior to other algorithms. And there are cases when memoization is used e.g. to compute factorial values less than 2**32 (a size of lookup table in this case is ~13). –  J.F. Sebastian Jan 30 '09 at 0:07
I still must be missing some subtlety of the question. If the lookup is theoretically worse than the calculation, we simply need to imagine a more complex calculation, no? –  Jon Ericson Jan 30 '09 at 8:25
Obviously, memoization is useful in many, many situations. It is clearly the best solution for a wide range of problems because the space used is trivial. But when the space used is substantial enough, the calculation wins out. My answer is that memoization, universally applied eventually fails. –  Jon Ericson Jan 30 '09 at 8:31

Not quite on the mark, but backtracking-based regular expressions have an exponential worst case versus O(N) for DFA-based regular expressions, yet backtracking-based regular expressions are almost always used rather than DFA-based ones.



The power that backreferences add comes at great cost: in the worst case, the best known implementations require exponential search algorithms.

Regular Expression Engines:

This method (DFA) is really more efficient, and can even be adapted to allow capturing and non-greedy matching, but it also has important drawbacks:

  • Lookarounds are impossible
  • Back-references are also impossible
  • Regex pre-compilation is longer and takes more memory

On the bright side, as well as avoiding worst-case exponential running times, DFA approaches avoid worst-case stack usage that is linear in the size of the input data.


share|improve this answer
It is a good example. Do you know why is it so? –  J.F. Sebastian Jan 29 '09 at 5:06
Eh, mostly I'm unacquainted with any compelling reason not to use a DFA-based approach. Maybe the alternative gives you more power or terser syntax, but by the time you need any of that stuff I would argue that you look to something other than regular expressions. Obviously I'm not a Perl hacker. –  Ellery Newcomer Jan 29 '09 at 19:10
I've added drawbacks of Thompson NFA compared to backtracking regex engines –  J.F. Sebastian Feb 1 '09 at 4:01
Due to DFA-based engines do not support backreferences they have narrower application domain than backtracking engines. My question is about algorithms with the same power (application domain). –  J.F. Sebastian Feb 1 '09 at 4:10
@J.F.: Actually DFAs can be adapted to allow capturing and non-greedy matching at no extra asymptotic cost -- this is mentioned in the swtch.com link you gave. Edited. –  j_random_hacker Jan 15 '11 at 12:13

Mergesort versus Quicksort

Quick sort has an average time complexity of O(n log n). It can sort arrays in place, i.e. a space complexity of O(1).

Merge sort also has an average time complexity of O(n log n), however its space complexity is much worse: Θ(n). (there is a special case for linked lists)

Because of the worst case time complexity of quick sort is Θ(n^2) (i.e. all elements fall on the same side of every pivot), and mergesort's worst case is O(n log n), mergesort is the default choice for library implementers.

In this case, I think that the predictability of the mergesort's worst case time complexity trumps quicksorts much lower memory requirements.

Given that it is possible to vastly reduce the likelihood of the worst case of quicksort's time complexity (via random selection of the pivot for example), I think one could argue that mergesort is worse in all but the pathological case of quicksort.

share|improve this answer
Which libraries prefer mergesort over quicksort? –  J.F. Sebastian Jan 29 '09 at 3:18
Libraries that have to provide stable sorts –  Ellery Newcomer Jan 29 '09 at 4:35
Both perl and Java's current implementations use mergesort. .net uses quicksort. Python uses "timsort". –  jamesh Jan 29 '09 at 18:26
To summarize: mergesort requires more memory but it is stable. BTW, a not naive quicksort implementation is worse-case O(n*log(n)). See pivot selection algorithm in @Sasha's answer. –  J.F. Sebastian Jan 29 '09 at 22:38
The example is good but mergesort is not preferable over quicksort in all practical situations. –  J.F. Sebastian Jan 29 '09 at 22:40

When calculating the median of a group of numbers, you can use an algorithm very similar to quicksort. You partition around a number, and all the bigger ones go to one side, and all the smaller ones go the other side. Then you throw away one side and recursively calculate the median of the larger side. This takes O(n^2) in the worst case, but is pretty fast (O(n) with a low constant) in the average case.

You can get guaranteed worst-case O(n) performance, with a constant of about 40. This is called the median of medians algorithm. In practice, you would never use this.

share|improve this answer

One example is from computational geometry. Polygon triangulation has worst case O(N) algorithm due to Chazelle, but it is almost never implemented in practice due to toughness of implementation and huge constant.

share|improve this answer
Does anybody know is there any implementation of this algorithm around? –  kolistivra Nov 21 '10 at 20:59

There exists a polynomial time algorithm for determining primality, but in practice, it's always faster to use an exponential time algorithm or to perform enough probabilistic calculations to have sufficient certainty.

share|improve this answer

I've always understood the term 'worse is better' to relate to problems with correct solutions that are very complex where an approximate (or good enough) solution exists that is relatively easier to comprehend.

This makes for easier design, production, and maintenance.

share|improve this answer
My question has narrower meaning as in worse time complexity but better otherwise. –  J.F. Sebastian Jan 23 '09 at 2:28

There's an O(n) algorithm for selecting the k-th largest element from an unsorted set, but it is rarely used instead of sorting, which is of course O(n logn).

share|improve this answer
I don't see any reason to use sorting for the tasks when nthlargest is applicable. It is in stdlib in many languages and it easy to implement if it is not. –  J.F. Sebastian Jan 23 '09 at 9:45
Is it really in stdlibs? I don't know of a linear time implementation in either C++, Java or Python. Can you provide some pointers? –  Rafał Dowgird Jan 23 '09 at 11:49
its in STL's algorithms: sgi.com/tech/stl/nth_element.html and it is very much used. –  shoosh Jan 23 '09 at 19:12
In Python's stdlib: heapq.nlargest() –  J.F. Sebastian Jan 29 '09 at 3:15
@J.F. Sebastian: Python's heapq.nlargest() is not O(n), but O(n log(k)). –  Rafał Dowgird Jan 29 '09 at 9:14

Insertion sort despite having O(n2) complexity is faster for small collections (n < 10) than any other sorting algorithm. That's because the nested loop is small and executes fast. Many libraries (including STL) that have implementation of sort method actually using it for small subsets of data to speed things up.

share|improve this answer
No doubt there are many examples when a specific solution is preferable for a specific task over a more general solution, but my question about solutions that have the same application domain. –  J.F. Sebastian Jan 29 '09 at 3:22

Monte carlo integration was already suggested but a more specific example is Monte Carlo pricing in finance is also a suggestion. Here the method is much easier to code and can do more things than some others BUT it is much slower than say, finite difference.

its not practical to do 20dimensional finite difference algorithms, but a 20 dimensional pricing execution is easy to set up.

share|improve this answer
You are write a 100**20 mesh cells (100 nodes in each directions) is hard to imagine in practice. –  J.F. Sebastian Jan 29 '09 at 5:12
Another application is a solving of partial differential equations for N-points probability density functions (number of cells is growing as nnodes**(N*ndim) ) –  J.F. Sebastian Jan 29 '09 at 5:17
i think in general 20-d fd algoritm is almost impossible :) I believe the rule of thumb is that FD is good for about 4 dimensions, and after that Montecarlo wins. In very high dimensions, the montecarlo may even be faster! –  simonjpascoe Jan 29 '09 at 6:42

The Spaghetti sort is better than any other sorting algorithm in that it is O(n) to set up, O(1) to execute and O(n) to extract the sorted data. It accomplishes all of this in O(n) space complexity. (Overall performance: O(n) in time and space both.) Yet, for some strange (obvious) reason, nobody uses it for anything at all, preferring the far inferior O(nlogn) algorithms and their ilk.

share|improve this answer
The reason it is not widely used is that it can't be implemented in O(n) on a classical computer. Classical architecture was implied in the question (though not explicitly) due to there is no point in discussing practical applications of an algorithm if a computer that can run it doesn't exist. –  J.F. Sebastian May 31 '10 at 8:31
Give me some seed cash -- say $50K -- and I'll implement the spaghetti sort for you robotically. It will still be less useful (by far!) than the mathematically inferior O(nlogn) algorithms because the constant factor is a tad high (where "tad" is more precisely defined as "six orders of magnitude or so"). –  JUST MY correct OPINION May 31 '10 at 9:27

Iterative Deepening

When compared to a trivial depth-first search augmented with alpha-beta pruning an iterative deepening search used in conjunction with a poor (or non-existent) branch ordering heuristic would result in many more nodes being scanned. However, when a good branch ordering heuristic is used a significant portion of the tree is eliminated due to the enhanced effect of the alpha-beta pruning. A second advantage unrelated to time or space complexity is that a guess of the solution over the problem domain is established early and that guess gets refined as the search progresses. It is this second advantage that makes it so appealing in many problem domains.

share|improve this answer
What algorithms have better time-complexity than algorithms based on "iterative deepening" strategy and why are they worse in all practical applications? –  J.F. Sebastian May 31 '10 at 4:33
Quick-sort has worst case time complexity of O(N^2)! 
It is considered better than other sorting algorithms 
like mergesort heapsort etc. which have O(N log n) time complexity 
in the worst case.
The reason may be the 
1.in place sorting 
3.very less amount of code involved.
share|improve this answer

Your Answer


