10
$\begingroup$

Big-O notation hides constant factors, so some $O(n)$ algorithms exist that are infeasible for any reasonable input size because the coefficient on the $n$ term is so huge.

Are there any known algorithms whose runtime is $O(f(n))$ but with some low-order $o(f(n))$ term that is so huge that for reasonable input sizes it completely dominates the runtime? I'd like to use an algorithm like this an an example in an algorithms course, as it gives a good reason why big-O notation isn't everthing.

Thanks!

$\endgroup$
  • $\begingroup$ Algorithms that first set up a large table and then do fast lookups in the table for each input item? If the table is large enough then the number of items has to be enormous to offset the cost of creating the table. Search engines are one example, if $n$ is the number of queries. $\endgroup$ – András Salamon Oct 5 '13 at 9:06
  • $\begingroup$ I've heard linear programming is like this. Simplex is exponential but faster than the polynomial algorithms in practice. $\endgroup$ – jmite Oct 5 '13 at 14:31
  • 1
    $\begingroup$ I don't know any algorithm that would fit your needs, but I'd look for something that has at most linear running time, since beyond that I would very much doubt the smaller terms could dominate the leading term for most reasonable inputs. But maybe k-way mergesort suits your needs, when used to sort big data? The problem there is to minimize the secondary memory accesses since those cost huge amounts of time - though I'm not entirely sure that that would be an appropriate example for what you want to demonstrate, and I don't really think it's simple enough to be illustrative. $\endgroup$ – G. Bach Oct 5 '13 at 15:41
  • $\begingroup$ somewhat similar to powerful algorithms too complex to implement, also see rjlipton blog on galactic algorithms $\endgroup$ – vzn Dec 4 '13 at 17:19
2
$\begingroup$

Cryptography is an example, if a degenerate one. For example, breaking AES encryption is $O(1)$ — all you have to do is find the right key among a finite number, $2^{128}$ or $2^{192}$ or $2^{256}$ depending on the key size (assume that enough of the plaintext is known to determine the key unambiguously). However even $2^{128}$ operations would take all of the computers today (a billion or thereabouts, each doing about a billion operations per sceond) more than the lifetime of the universe (about a billion billion seconds).


A slightly different way to illustrate why big-O isn't everything is to remark that we sometimes use a different algorithm for small input sizes. For example, take quicksort. With the right choice of pivot (which is a tricky business!), it's $O(n \lg n)$. Quicksort operates by divide-and-conquer: every instance involves doing a lot of sorting of small arrays. For small arrays, quadratic methods such as insertion sort perform better. So for best performance, a quicksort of a large array involves a lot of runs of insertion sort for small sizes.

$\endgroup$
  • $\begingroup$ I don't think breaking encryption is a reasonable example here; one thing is that to analyse the problem of finding the correct key asymptotically, we would have to consider the theoretically available versions of Rijndael with non-constant key size, i.e. breaking the key for keys of size $n$. Otherwise we might just as well say that any algorithm that terminates performs in $\mathcal{O}(1)$ for fixed size input. $\endgroup$ – G. Bach Oct 5 '13 at 15:38
  • $\begingroup$ @G.Bach The point of this example is that it's infeasible (which complexity theory associates with high complexity) even though it's constant-time (in terms of the size of the ciphertext). $\endgroup$ – Gilles Oct 5 '13 at 15:41
  • 2
    $\begingroup$ I don't think your first example works. Since there are only finitely many options to check, the algorithm's runtime is $O(1)$, so there isn't a low-order $o(1)$ term that accounts for the full runtime. $\endgroup$ – templatetypedef Oct 6 '13 at 0:28
  • 1
    $\begingroup$ @templatetypedef Breaking the encryption of an AES-encrypted message is $O(1)$ in terms of the length of the message. $\endgroup$ – Gilles Oct 6 '13 at 18:10
1
$\begingroup$

Two examples come to mind from the field of parameterized complexity and FPT algorithms. This might not be exactly what you are looking for, but here goes.

Consider a graph problem, such as 3-COLORING or HAM-CYCLE. Both problems can be expressed in monadic second order logic, and therefore can be decided in linear time of graphs with bounded treewidth. This is a result of Bruno Courcelle, but the resulting algorithm is far from practical.

The other example is a deep result by Lenstra, saying that integer linear programs (ILP) with a constant number of variables can be solved in linear time. By additional work made by Ravi Kannan, we have that the integer programming feasibility problem can be solved with $O(p^{9p/2})L$ arithmetic operations in integers of $O(p^{2p}L)$ bits in size, where $p$ is the number of ILP variables and $L$ is the number of bits in the input. This again gives rise to FPT algorithms, that are only practical for very small instances.

$\endgroup$
  • 2
    $\begingroup$ Courcelle's theorem is impractical because of the huge constant on the $O(n)$ term, not because some $o(n)$ term dominates it on "small" inputs. (The constant grows as a tower of twos with height depending on the number of nested negations and quantifier alternations in the first-order formula.) $\endgroup$ – David Richerby Oct 6 '13 at 7:33
0
$\begingroup$

somewhat related to your question are algorithms that are known to have good performance theoretically but are not used on real problems due to impracticality on smaller instances. in other words like you request, the "advertised performance" is only possible for large inputs in theory, not seen in practical applications. this is sometimes reflected in the Big-Oh estimates, other times not exactly. some algorithms have good theoretical "performance" but are very logically complex and havent ever been implemented by anyone, and therefore the "performance" on practical instance sizes isnt even known, eg as with Maximum Flow problem.

$\endgroup$
  • $\begingroup$ But are those impractical because the low-order terms dominate or because the constants on the high-order terms are bad? $\endgroup$ – David Richerby Dec 4 '13 at 19:12
  • $\begingroup$ either, or a combination, it would be difficult to isolate in each case. effectively/practically its the same effect. $\endgroup$ – vzn Dec 4 '13 at 19:53
-1
$\begingroup$

This is kind of a joke but it has a serious side...

Quicksort. It's useful in practice because the $O(n\log n)$ terms dominate the $O(n^2)$ worst case that results from consistently choosing terrible pivots.

$\endgroup$
  • 1
    $\begingroup$ No, that's different. Quicksort is useful in practice because there is no quadratic term for typical input, no matter how large the size is. If the choice of pivot is bad for a data layout, quicksort exhibits quadratic behavior even for small input. $\endgroup$ – Gilles Oct 5 '13 at 13:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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