# Do real-world algorithms that greatly outperform in the class below exist? [closed]

Last night I was discussing with another programmer that even though something may be O(1), an operation which is O(n) may outperform it if there are is a large constant in the O(1) algorithm. He disagreed, so I've brought it here.

Are there examples of algorithms which greatly outperform those in the class below it? For example, O(n) being faster than O(1) or O(n2) being faster than O(n).

Mathematically this can be demonstrated for a function with an asymptotic upper bounds, when you disregard constant factors, but do such algorithms exist in the wild? And where would I find examples of them? What types of situations are they used for?

• Even for "big" algorithms, smaller is not necessarily better. For example, gaussian elimination is O(n^3), but there are algorithms that can do it in O(n^2), but the coefficient for the quadratic time algo is so huge that people just go with the O(n^3) one. Oct 6, 2011 at 23:41
• You have to add "... for real-world problems" or some such to make this a sensible question. Otherwise you only need to make `n` big enough to compensate for the constant (which is the point of big-O notation). Oct 7, 2011 at 9:25
• Don't take big-O notation for speed. Oct 7, 2011 at 19:06
• The point of big-O notation is not to tell you how fast an algorithm runs, but how well it scales. Oct 8, 2011 at 7:15
• I'm surprised nobody has mentioned the Simplex algorithm for solving LP. It has an exponential worst-case with a linear expected run-time. In practice, it is quite fast. It's trivial to construct a problem that exhibits the worst-case run-time as well. Also, it's heavily used. Apr 18, 2012 at 14:59

Lookups in very small, fixed data tables. An optimized hash table may be O(1) and yet slower than a binary search or even a linear search due to the cost of the hash calculation.

• More precisely, hashtable lookup is O(m) where m is the size of the key. You only get to call that O(1) if the key size is constant. Also, usually that's amortized - otherwise the table can't grow/shrink. Ternary trees can often beat hash tables for string lookups in contexts where the strings quite often aren't found - the ternary tree search will often discover that the key isn't present while still checking the first character or two of the string, where the hashtable version hasn't yet calculated the hash.
– user8709
Oct 7, 2011 at 10:17
• I love Loren Pechtel's answer and Steve314's first comment. I've actually seen this happen. If you create a Java class that has a hashcode() method that takes too long to return the hash value (and doesn't/can't cache it), then using instances of such a class in a hash-type collection (like HashSet) will make that collection ALOT slower than an array-type collection (like ArrayList). Oct 7, 2011 at 15:02
• @Steve314: why do you assume hash functions are O(m) where m is the size of the key? Hash functions can be O(1) even if you are dealing with strings (or other complex type). There is no too much value to put it in formal definition than simply realizing the hash function could significantly change the complexity if a wrong data structure (hash table) is chosen for your input (key size is unpredictable). Oct 7, 2011 at 19:24
• @Steve314: Note that I said fixed data tables. They don't grow. Also, you only get O(1) performance from a hash table if you can optimize the key to ensure there are no collisions. Oct 7, 2011 at 20:09
• @Loren - strictly, if the table has a fixed size, there's a constant maximum amount of time you can spend looking for an free space. That is, at most, you can need to check n-1 already-filled slots where n is the constant table size. So a fixed-size hash table really is O(1), without needing amortized analysis. This doesn't mean you don't care about the accesses getting slower as the table fills - only that it isn't what big O expresses.
– user8709
Oct 8, 2011 at 6:10

Matrix multiplication. The naïve O(n^3) algorithm is often used in practice as faster than Strassen's O(n^2.8) for small-ish matrices; and Strassen's is used instead of the O(n^2.3) Coppersmith–Winograd algorithm for larger matrices.

• en.wikipedia.org/wiki/… Oct 7, 2011 at 9:32
• Coppersmith-Winograd is NEVER used. Implementing it would be a horrid task in itself and the constant is so bad it would be unfeasible even for modern scientific matrix problems. Nov 3, 2011 at 19:50

A simple example is the difference between various sorting algorithms. Mergesort, Heapsort, and some others are O(n log n). Quicksort is O(n^2) worst case. But often Quicksort is faster, and in fact it performs on average like O(n log n). More info.

Another example is the generation of a single Fibonacci number. The iterative algorithm is O(n), whereas the matrix-based algorithm is O(log n). Still, for the first couple of thousand Fibonacci numbers, the iterative algorithm is probably faster. This also depends on the implementation of course!

Algorithms with a better asymptotic performance may contain costly operations that are not necessary with an algorithm with worse performance but simpler operations. In the end, the O-notation only tells us something about performance when the argument it operates on increases dramatically (approaches infinity).

• This is a great explanation of Big-O, but fails to address the meat of the question, which is for specific cases where an O(n) algorithm will be faster than an O(1). Oct 7, 2011 at 5:07
• The Fibonacci number one is slightly off. The output size is exponential in the input size, so it's a difference between O(lg n * e^n) vs O(lg lg n * e^n). Oct 7, 2011 at 8:17
• Addendum: at best. The matrix-based algorithm does multiplication with numbers on the order of 1.5^n, so O(lg lg n * n e^n) might be the best bound provable. Oct 7, 2011 at 8:29
• Quicksort is normally described as O(n log n) expected performance anyway - the worst case is pretty unlikely for random inputs, and building some randomness into a prepass or into the pivot selection means the worst case overall is very unlikely for significant input sizes. The worst-case is less relevant than the fact that quicksort is (1) very simple, and (2) very cache-friendly, both of which lead to significantly better constant factors than in many other sorting algorithms.
– user8709
Oct 7, 2011 at 11:03
• (2) is precisely the sort of external consideration that must be taken into account when looking at big-O performance. Algorithmically, Mergesort should always outperform Quicksort, but resource usage and cache locality generally reverse their real-world performance positions. Apr 18, 2012 at 18:17

Note: Please read the comments by @back2dos below and other gurus, as they are in fact more helpful than what I have written - Thanks for all contributors.

I think from the chart below (taken from: Big O notation, search for "The Pessimistic Nature of Algorithms:"), you can see that O(log n) is not always better than say, O(n). So, I guess your argument is valid. • The question wanted specific real world examples of algorithms. This does not have any as it stands. Oct 7, 2011 at 9:09
• You can see nothing on that graph, that would answer the question. It is misleading. This graph merely plots the functions `y = 1`, `y = log x`, and so on and the intersection of `y = 1` and `y = x` is actually the point `(1,1)`. If this really were correct, than it would tell you, that algorithms of higher complexity can be faster for 0 to 2 entries, which is something people hardly would care for. What the graph completely fails to take into account (and what the perceivable performance difference in question comes from) is constant factors. Oct 7, 2011 at 9:12
• @Samuel Walker, thanks for the comment. The link provided (Link-1) has some examples of algorithms per category. Oct 7, 2011 at 9:14
• @back2dos: The graph on it's own does not answer the question, but can be used to answer it. The shape of each displayed function is the same for any scale and constant factor. With this the graph shows that given combination of functions, there is a range of inputs for which one is smaller and a range of inputs for which the other is. Oct 7, 2011 at 11:42
• @dan_waterworth, you're right, I'll concede that point and remove that comment. Nevertheless, the answer is incorrect or misleading in two respects: 1) The whole point of Big-O is that it gives an upper bound on complexity; it's only meaningful for large n because we explicitly toss out smaller terms which are overwhelmed by the largest term as n grows. 2) The point of the question is to find examples of two algorithms where the one with the higher Big-O bound outperforms one with a lower bound. This answer fails because it doesn't give any such examples. Oct 7, 2011 at 13:18

For practical values of `n`, yes. This comes up a lot in CS theory. Often there is a complicated algorithm that has technically better big-Oh performance, but the constant factors are so large as to make it impracticaly.

I once had my computational geometry professor describe an algorithm for triangulating a polygon in linear time, but he finished with "very complicated. I don't think anyone's actually implemented it" (!!).

Also, fibonacci heaps have better characteristics than normal heaps, but are not very popular because they don't perform as well in practice as regular heaps. This can cascade to other algorithms that use heaps - for instance, Dijkstra's shortest-paths is mathematically faster with a fibonacci heap, but usually not in practice.

• It's faster for huge graphs on the order of 100,000 or so vertices. Nov 3, 2011 at 19:51
• Fibonacci heaps were my first (actually, second) thought as well. Apr 18, 2012 at 21:07

Compare inserting into a linked list and inserting into a resizable array.

The amount of data has to be fairly large for the linked list O(1) insertion to be worthwhile.

A linked list has extra overhead for next pointers and dereferences. A resizable array has to copy data around. That copying is O(n), but in practice very fast.

• A resizable array is doubled in size each time it fills, so the average cost of resizing per insertion is O(1). Oct 7, 2011 at 15:21
• @kevincline, yes but the O(n) comes from having to move all of the elements after the insertion point forward. Allocation is amortized O(1) time. My point is that that movement is still very fast, so in practice is usually beats linked lists. Oct 7, 2011 at 15:46
• The reason contiguous arrays are so fast in comparison to linked lists is due to processor caching. Traversing a linked list will cause a cache miss for every element. To get the best of both worlds you should use an unrolled linked list. Apr 19, 2012 at 7:00
• Resizable arrays don't always copy. It depends on what it's running on and if there's anything in the way. Same for the doubling size, implementation specific. The roll over roll over thing though is a problem. Linked lists are usually best for queues of unknown size though rotary buffers give queues a run for their money. In other cases linked lists are useful because allocation or expansion simply isn't going to let you have contiguous stuff all the time so you'll need a pointer anyway. Jan 9, 2019 at 23:45
• @jgmjgm, if you insert into the middle of a resizable array, its absolutely does copy the elements after that. Jan 11, 2019 at 15:55

The Big-Oh notation is used to describe a function's growth-rate, so it is possible that an O(1) algorithm will be faster, but only up to a certain point (the constant factor).

Common notations:

O(1) - The number of iterations (sometimes you can refer to this as user-time spent by the function) is not dependent on the size of the input, and is in fact constant.

O(n) - The number of iterations grows in a linear proportion to the size of the input. Meaning - if the algorithm iterates through any input N, 2 * N times, it is still considered O(n).

O(n^2) (quadratic) - The number of iterations is the input size squared.

• To add an example to an otherwise excellent answer: an O(1) method may take 37 years per call, whereas an O(n) method may take 16*n microseconds per call. Which is faster? Oct 7, 2011 at 7:14
• I completely fail to see how this answers the question. Oct 7, 2011 at 7:53
• I understand big-O. This does not address the actual question, which is specific examples of functions where algorithms with a lower big-O are outperformed by those with a higher big-O. Oct 7, 2011 at 7:54
• When you put the question in the form "Are there examples ...", someone is inevitably going to answer "Yes." without giving any. Oct 7, 2011 at 8:40
• @rakslice: Maybe so. However this site demands explanation (or better yet proof) of any statements you make. Now the best way to proof, that there are such examples is to give one ;) Oct 7, 2011 at 9:06

Regex libraries are usually implemented to do backtracking which has worst case exponential time rather than DFA generation which has a complexity of `O(nm)`.

Naive backtracking can be a better performer when the input stays on the fast path or fails without the need to backtrack excessively.

(Although this decision isn't just performance based, it's also to allow back references.)

• I think it's also partly historical--the algorithm for turning a regular expression into a DFA was patented when some of the earlier tools (sed and grep, I guess) were being developed. Of course I heard this from my compilers professor who wasn't entirely sure, so this is a third-hand account. Apr 19, 2012 at 6:44

An `O(1)` algorithm:

``````def constant_time_algorithm
one_million = 1000 * 1000
sleep(one_million) # seconds
end
``````

An `O(n)` algorithm:

``````def linear_time_algorithm(n)
sleep(n) # seconds
end
``````

Clearly, for any value of `n` where `n < one_million`, the `O(n)` algorithm given in the example will be faster than the `O(1)` algorithm.

While this example is a bit facetious, it is equivalent in spirit to the following example:

``````def constant_time_algorithm
end

def linear_time_algorithm(n)
i = 0
while i < n
i += 1
do_a_minute_amount_of_work_that_takes_nanoseconds
end
end
``````

You must know the constants and coefficients in your `O` expression, and you must know the expected range of `n`, in order to determine a priori which algorithm will end up being faster.

Otherwise, you must benchmark the two algorithms with values of `n` in the expected range in order to determine a posteriori which algorithm ended up being faster.

Sorting:

Insertion sort is O(n^2) but outperforms others O(n*log(n)) sorting algorithms for small number of elements.

This is the reason why most sort implementations use a combination of two algorithms. E.g. use merge sort to break down large arrays until they reach a array certain size, then use insertion sort to sort the smaller units and merge them again with merge sort.

See Timsort the current default implementation of Python and Java 7 sorting that use this technique.

The unification algorithm used in practice is exponential in the worst case, for some pathological inputs.

There is a polynomial unification algorithm, but it is too slow in practice.

Bubblesort in memory can outperform quicksort when the program is being swapped to disk or need to read every item from disk when comparing.

This should be an example he can relate to.

• Doesn't the quoted complexities on quicksort and bubblesort assume O(1) random memory access? If this is no longer the case, wouldn't quicksorts complexity need to be reexamined? Oct 7, 2011 at 10:28
• @ViktorDahl, the item access time is not part of what is traditionally being measured in sort algorithm complexities so "O(1)" is not the right choice of words here. Use "constant time" instead. PHK wrote an article a while back about sort algorithms knowing that some items are more expensive to retreive than others (virtual memory) - queue.acm.org/detail.cfm?id=1814327 - you might find it interesting.
– user1249
Oct 7, 2011 at 10:55
• I see my mistake now. One usually measures the number of comparisons, and of course they are not affected by the speed of the storage medium. Also, thanks for the link. Oct 7, 2011 at 12:03

Often the more advanced algorithms assume a certain amount of (expensive) setup. If you only need to run it once, you might be better off with the brute-force method.

For example: binary search and hash table lookup are both much faster per lookup then a linear search, but they require you to sort the list or build the hash table, respectively.

The sort will cost you N log(N) and the hash table will cost at least N. Now if you are going to be doing hundreds or thousands of lookups, that is still an amortized savings. But if you only need to do one or two lookups, it might just make sense to just do the linear search and save the startup cost.

Decryption is often 0(1). For example the key space for DES is 2^56, so decryption of any message is a constant time operation. Its just that you have a factor of 2^56 in there so its a really big constant.

• Isn't decryption of a message O(n), where n is proportional to the size of the message? As long as you have the correct key, the size of the key doesn't even enter into consideration; some algorithms have minimal or no key setup/expansion processes (DES, RSA - note that key generation may still be a complex task, but that has nothing to do with key expansion) whereas others are extremely complex (Blowfish comes to mind), but once it's done, the time to do the actual work is proportional to the size of the message, hence O(n).
– user
Oct 7, 2011 at 11:12
• You probably mean cryptananalysis rather than decryption? Oct 7, 2011 at 11:58
• Well, yes, there are any number of things that you can take to be constant and declare an algorithm to be O(1). [sorting implicitly assumes the elements take a constant amount of time to compare, for example, or any math with non-bignum numbers] Oct 7, 2011 at 18:56

Different implementations of sets spring to my mind. One of the most naive is implementing it over a vector, which means `remove` as well as `contains` and therefore also `add` all take O(N).
An alternative is to implement it over some general purpose hash, which maps input hashes to input values. Such a set implementation performs with O(1) for `add`, `contains` and `remove`.

If we assume N is about 10 or so, then the first implementation is probably faster. All it has to do to find an element is to compare 10 values to one.
The other implementation will have to start all sorts of clever transformations, which can be a lot more expensive, than making 10 comparisons. With all the overhead, you might even have cache misses and then it really doesn't matter how fast your solution is in theory.

This doesn't mean, that the worst implementation you can think of will outperform a decent one, if N is small enough. It simply means for sufficiently small N, that a naive implementation, with low footprint and overhead can actually require less instructions and cause less cache misses than an implementation that puts scaleability first, and will therefore be faster.

You can't really know how fast anything is in a real world scenario, until you put it into one and simply measure it. Often results are surprising (at least to me).

Yes, for suitably small N. There will always be a N, above which you will always have the ordering O(1) < O(lg N) < O(N) < O(N log N) < O(N^c) < O(c^N) (where O(1) < O(lg N) means that at an O(1) algorithm will take fewer operations when N is suitably large and c is a some fixed constant that is greater than 1).

Say a particular O(1) algorithm takes exactly f(N) = 10^100 (a googol) operations and an O(N) algorithm takes exactly g(N) = 2 N + 5 operations. The O(N) algorithm will give greater performance until you N is roughly a googol (actually when N > (10^100 - 5)/2), so if you only expected N to be in the range of 1000 to a billion you would suffer a major penalty using the O(1) algorithm.

Or for a realistic comparison, say you are multiplying n-digit numbers together. The Karatsuba algorithm is at most 3 n^(lg 3) operations (that is roughly O(n^1.585) ) while the Schönhage–Strassen algorithm is O(N log N log log N) which is a faster order, but to quote wikipedia:

In practice the Schönhage–Strassen algorithm starts to outperform older methods such as Karatsuba and Toom–Cook multiplication for numbers beyond 2^2^15 to 2^2^17 (10,000 to 40,000 decimal digits).

So if you are multiplying 500 digit numbers together, it doesn't make sense to use the algorithm that's "faster" by big O arguments.

EDIT: You can find determine f(N) compared g(N), by taking the limit N->infinity of f(N)/g(N). If the limit is 0 then f(N) < g(N), if the limit is infinity then f(N) > g(N), and if the limit is some other constant then f(N) ~ g(N) in terms of big O notation.

The simplex method for linear programming can be exponential in the worst case, while relatively new interior point algorithms can be polynomial.

However, in practice, the exponential worst case for the simplex method doesn't come up -- the simplex method is fast and reliable, while early interior point algorithms were far too slow to be competitive. (There are now more modern interior point algorithms which are competitive -- but the simplex method is, too...)

Ukkonen's algorithm for building suffix tries is O(n log n). It has the advantage of being "on-line" - that is, you can incrementally append more text.

Recently, other more complex algorithms have claimed to be faster in practice, largely because their memory access has higher locality, thus improving processor cache utilization and avoiding CPU pipeline stalls. See, e.g., this survey, which claims that 70-80% of processing time is spent waiting for memory, and this paper describing the "wotd" algorithm.

Suffix tries are important in genetics (for matching gene sequences) and, somewhat less importantly, in the implementation of Scrabble dictionaries.

There's always the fastest and shortest algorithm for any well-defined problem. It's only purely theoretically the (asymptotically) fastest algorithm though.

Given any description of a problem P and an instance for that problem I, it enumerates all possible algorithms A and proofs Pr, checking for each such pair whether Pr is a valid proof that A is the asymptotically fastest algorithm for P. If it finds such a proof, it then executes A on I.

Searching for this problem-proof pair has complexity O(1) (for a fixed problem P), so you always use the asymptotically fastest algorithm for the problem. However, since this constant is so unspeakably enormous in nearly all cases, this method is completely useless in practice.

Many languages/frameworks use naive pattern matching to match strings instead of KMP. We look for string like Tom, New York rather than ababaabababababaababababababab.