As you know, big O notation hides all constants. For instance, both runtimes $T_1=n$ and $T_2=10^{10}n$ are considered to be linear ($\mathcal{O(n)}$). Is there an iconic problem whose best known solution has a terrible (large) constant in the runtime expression?
$\begingroup$
$\endgroup$
4
-
2$\begingroup$ The Wikipedia article doesn't list the constants, but Matrix multiplication comes to mind. $\endgroup$– StefCommented Nov 11, 2023 at 10:54
-
$\begingroup$ It doesn’t list the constants because they are dependent on the precise machine model, especially given the linear speedup theorem. (Though in my opinion this only proves that “the number of steps performed” is the wrong way to measure time complexity.) $\endgroup$– user3840170Commented Nov 11, 2023 at 11:46
-
$\begingroup$ Are there any actual numbers for the constant for matrix multiplication algorithms with best asymptotic behaviour? $\endgroup$– gnasher729Commented Nov 11, 2023 at 20:20
-
$\begingroup$ @user3840170 That’s cowardice. I can buy a computer that can hold three 240,000 x 240,000 double precision arrays. How long does it take to multiply the first two using a single modern Intel, AMD or Arm processor? With a factor 5 either way? Naive implementation optimised to use caches will take around 2 months. Less if I try very, very hard. Strassen might be ten times faster. $\endgroup$– gnasher729Commented Nov 11, 2023 at 20:27
Add a comment
|
4 Answers
$\begingroup$
$\endgroup$
2
Such algorithms are called Galactic Algorithms.
answered Nov 9, 2023 at 21:16
-
1$\begingroup$ I wanted to mention Hutter search but it is already in the list :) Also related: Gödel machine. $\endgroup$– StevenCommented Nov 9, 2023 at 21:44
-
10$\begingroup$ While the wikipedia article is great, embellishing this answer would be good as well. Most of those are cases of polynomial exponent shaving (dropping ^x to ^x-epsilon), but not all of them (and those exceptions would be worth mentioning). Looking at the list, the Sub-Graph problem passes, and maybe TSP (as it is a better answer). And Hutter deserves an honourable explicit mention. $\endgroup$– YakkCommented Nov 10, 2023 at 15:05
$\begingroup$
$\endgroup$
4
A simple one: Given n chess positions, find an optimal move for each position.
The game of chess is finite, so finding an optimal move for any position is O(1), and for n positions it is O(n). With a huge constant.
-
4$\begingroup$ Pursuing this example further, this can even be solved in time $A * n + B$ with $A$ fairly small (but $B$ ridiculously huge): list all possible chess positions, make a table of the optimal move in all of them, and then just look up the given input positions in the table $\endgroup$ Commented Nov 12, 2023 at 10:25
-
$\begingroup$ Now in practice (practice haha…) there are so many chess positions that the physical lookup table would be many light years in size and any lookup would take many years. $\endgroup$ Commented Nov 12, 2023 at 19:20
-
$\begingroup$ Yes, that's the whole point of this example... $\endgroup$ Commented Nov 13, 2023 at 6:50
-
1$\begingroup$ You can do something similar for any problem with a large runtime. Just fix the size of the input and then any algorithm becomes O(1). I suppose chess is a nice example since it's a real-world case where we focus on a fixed problem size. Rather than something artifical like "n instances of 3SAT with 1000 variables" which would also be O(n). $\endgroup$ Commented Nov 13, 2023 at 23:47
$\begingroup$
$\endgroup$
To add another perspective on this: there is a class of problems known as fixed parameter tractable (FPT) which has been studied extensively. In this area of research, one studies problems that, given a fixed additional integer parameter $k$ on the input, can be solved in polynomial time.
For example, suppose you are given a graph $G$ such that the tree-width of the graph is a known parameter $k$. Then one studies problems that are decidable in time $$ f(k) \cdot \text{polynomial}(|G|) $$
where $f$ is some function purely depending on $k$. So if $k$ is fixed, then these are polynomial time algorithms.
But the problem is that typically, the function $f$ turns out to be extremely fast growing. For example, $f$ might be exponential, or doubly exponential, or even non-elementary. So a problem might be FPT, but for, say, tree-width 4 or 5, you would already get a huge, astronomical constant in front of the polynomial.
answered Nov 11, 2023 at 17:50
$\begingroup$
$\endgroup$
Another simple one, that turned up in another question. Given a finite set S, sorting any array of elements of S can be sorted in linear time using counting sort (or without any additional storage: By moving every element s of S to the beginning of the array). This is linear instead of n log n, but has the size of S as a constant factor.
Problem: Sort any array of 256 bit integers in linear time.