Timeline for Worst known algorithm in terms of Big-O (more precisely Big-theta)?
Current License: CC BY-SA 4.0
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 23, 2022 at 10:03 | history | edited | Martin Sleziak | CC BY-SA 4.0 |
http -> https (the question was bumped anyway)
|
| Jun 16, 2015 at 18:21 | comment | added | clahey | There's no reason that computing the A(n)th digit of pi necessarily requires computing A(n). That would be like saying that computing A(n) mod 2 requires computing A(n), which it doesn't seem to (it appears to always be 1, but I haven't done all the necessary math.) Both are of the form f(A(n)). I agree that there's probably no shared structure, but that doesn't lead to a proof that there's no shared structure. | |
| May 19, 2011 at 21:03 | comment | added | Joel David Hamkins | Tom, yes, that would be faster, a polynomial time speed-up. But this is a actually a very mild improvement in light of the huge cost of computing $A(n)$, which dominates this algorithm. After all, the Ackermann function grows so rapidly that $A(n)$, $\log(A(n))$, $2^{A(n)}$ and even $2\uparrow A(n)$ all seem basically in the same ballpark (for example, these differences matter far far less than simply going to $A(n\pm 1)$), and so it is the difficulty of computing $A(n)$ that matters here, swamping any difficulty of computing $\pi$. | |
| May 19, 2011 at 15:37 | comment | added | Tom Church | @Joel, re: "it is not clear how one could improve the algorithm to make it faster." As soon as $n>3$ a huge speedup will be provided by using a spigot algorithm, which computes individual digits of $\pi$ without computing the preceding digits. en.wikipedia.org/wiki/Bailey-Borwein-Plouffe_formula | |
| May 19, 2011 at 13:46 | comment | added | Joel David Hamkins | Yes, I think that is right. | |
| May 19, 2011 at 13:41 | comment | added | Joseph O'Rourke | @Joel: I accept your point---You are correct! In practice one cares about matching a lower bound on all algorithms under a particular model with an upper bound. And this is often the route to $\Theta()$. | |
| May 19, 2011 at 13:33 | comment | added | Joel David Hamkins | An algorithm is correctly claimed as $\Theta(\cdot)$ if that is the asymptotic running time of that particular algorithm. It has nothing to do with whether there are other, quicker algorithms for the same problem. For exampe, my algorithm above has time complexity $\Theta(a(n))$, where $a(n)$ is the time to compute $A(n)$, even though I have no idea if there might be a quicker algorithm. | |
| May 19, 2011 at 13:10 | comment | added | Joseph O'Rourke | @Joel: I should have said: "...no algorithm, under a particular model of computation." For example, sorting has a lower bound of $\Omega( n \log n)$ in the algebraic decision-tree model, and various algorithms achieve $O( n \log n )$ and so are claimed as $\Theta(n \log n)$. | |
| May 19, 2011 at 13:01 | comment | added | Joel David Hamkins | In particular, I dispute your claim that a quoted $\Theta()$ bound means that it is known that no algorithm can do better---we very rarely know such information. Rather, a quoted $\Theta()$ bound describes the known running time of a particular proposed algorithm. | |
| May 19, 2011 at 12:59 | comment | added | Joel David Hamkins | Joseph, the running-time concept is a feature of the algorithm, not of the problem that the algorithm solves. Indeed, we very rarely have information about the best possible time bound to solve a given problem. For example, knowing such information for certain problems would enable us to solve the P vs. NP problem. | |
| May 19, 2011 at 12:54 | comment | added | Joseph O'Rourke | @Joel: Concerning your first sentence, wouldn't it be more natural to focus on the time complexity of any algorithm that solves a particular problem, rather than on the time complexity of a specific algorithm? So usually a quoted $\Theta()$ bound means that no algorithm can do better, and some algorithm achieves that bound. | |
| May 19, 2011 at 12:34 | history | answered | Joel David Hamkins | CC BY-SA 3.0 |