<p>The algorithm of <a href="https://doi.org/10.1145/1066100.1066101" rel="nofollow noreferrer">Paturi, Pudlák, Saks and Zane</a> (PPSZ) for <span class="math-container">$k\text{-}   \mathrm{SAT}$</span> had been known to have a running time of <span class="math-container">$O(1.364^n)$</span> for <span class="math-container">$3\text{-}\mathrm{SAT}$</span>, with a better bound of <span class="math-container">$O(1.308^n)$</span> for formulas guaranteed to have a unique satisfying assignment.
Later <a href="https://doi.org/10.1109/FOCS.2011.22" rel="nofollow noreferrer">Hertli</a> gave an improved analysis showing that this improved run-time bound also holds for the general case, thus showing PPSZ to be the best algorithm for <span class="math-container">$3\text{-}\mathrm{SAT}$</span> known at the time.</p>
<p>There is now also a further improved analysis of the algorithm, yielding the bound <span class="math-container">$O(1.307^n)$</span> for <span class="math-container">$3\text{-}\mathrm{SAT}$</span>, due to <a href="https://eccc.weizmann.ac.il/report/2021/069/" rel="nofollow noreferrer">Scheder</a>.</p>

CC BY-SA 4.0
2019-08-26T02:25:53.107Z
This is a really satisfying answer! I think it and the Union Find examples are the best examples of what I was hoping for.
Rob Simmons
CC BY-SA 4.0
2019-08-14T12:18:32.230Z
2024-09-18T14:22:34.950Z
2024-09-18T14:22:34.950Z
Jan Johannsen
<p>The <a href="https://en.wikipedia.org/wiki/Disjoint-set_data_structure" rel="noreferrer">Union-Find algorithm,</a> which Tarjan<sup>1</sup> showed had complexity <span class="math-container">$n \alpha(n)$</span>, where <span class="math-container">$\alpha(n)$</span> is the inverse Ackermann function, had been analyzed previously by several people. According to Wikipedia, it was invented by Galler and Fischer<sup>2</sup>, but this seems to be incorrect, as they did not have all the components of the algorithm needed to make it run that quickly.</p>

<p>Based on brief scans of the papers, it appears that the algorithm was invented by Hopcroft and Ullman<sup>3</sup>, who gave an (incorrect) <span class="math-container">$O(n)$</span> time bound. Fischer<sup>4</sup> then found the mistake in the proof and gave an <span class="math-container">$O(n \log\log n)$</span> time bound. Next, Hopcroft and Ullman<sup>5</sup> gave an <span class="math-container">$O(n \log
^*n)$</span> time bound, after which Tarjan<sup>1</sup> found the (optimal) <span class="math-container">$O(n \alpha(n))$</span> time bound.</p>

<p><sup>1</sup> R.E. Tarjan, "Efficiency of a good but not linear set union algorithm" (1975). <br>
<sup>2</sup> B.S. Galler and M.J. Fischer, "An improved equivalence algorithm" (1964). <br>
<sup>3</sup> J.E. Hopcroft and J.D. Ullman, "A linear list merging algorithm" (1971).<br>
<sup>4</sup> M.J. Fischer, "Efficiency of equivalence algorithms" (1972).<br>
<sup>5</sup> J.E. Hopcroft and J.D. Ullman, "Set-merging algorithms" (1973).</p>

CC BY-SA 4.0
2019-08-13T16:13:45.963Z
The history of this data structure is a little unclear to me and it would be nice to investigate it. I skimmed the Galler and Fischer article, and it seems to describe the Disjoint Sets Forest (DSF) data structure but without the crucial path compression (PC) and weighted union (WU) heuristics. Hopcroft and Ullman attribute DSF with PC and without WU to Tritter, citing Knuth. I am not sure if DSF with both PC and WU was proposed in a published paper prior to Hopcroft and Ullman's paper, although I wouldn't be surprised if it was.
Sasho Nikolov
CC BY-SA 4.0
2019-08-13T17:21:00.870Z
@Sasho: This should all be checked, as it's based on brief scans of the papers. Tarjan attributes DSF with both PC and WU to Michael Fischer, in "Efficiency of equivalence algorithms" (1972), which gives an $O(n \log\log n)$ running time for it. Scanning Fischer's paper, he seems to attribute the algorithm to Hopcroft and Ullman in "A linear list merging algorithm", but they give an $\Theta(n)$ running time for it, the proof of which Fischer shows is incorrect. Tarjan says that Hopcroft and Ullman, in "Set-merging algorithms" redeem themselves by giving an $O(n \log^* n)$ bound.
Peter Shor 
CC BY-SA 4.0
2019-08-10T12:18:04.850Z
2019-12-11T19:34:51.230Z
2019-12-11T19:34:51.230Z
Peter Shor 
<p>The <a href="https://weakdh.org/imperfect-forward-secrecy-ccs15.pdf" rel="noreferrer">Logjam Attack</a> mentions that analysis of the general number field sieve (as applied to computing discrete logarithms over <span class="math-container">$\mathbb{F}_p$</span>) descent step was tightend, see top left of the 3rd page. As this is the only step that can't be pre-computed (if <span class="math-container">$\mathbb{F}_p$</span> is fixed), its efficiency was instrumental to their attack.</p>

<p>The initial analysis appears to be in <a href="https://www.dmgordon.org/papers/log.pdf" rel="noreferrer">Gordon 92</a>, where descent was costed similarly to precomputation, at <span class="math-container">$L_p(1/3, 3^{2/3})$</span>. The tighter analysis seems to be from <a href="https://hal.univ-lorraine.fr/tel-01750438" rel="noreferrer">Barbulescu's thesis</a>, where descent is costed at <span class="math-container">$L_p(1/3, 1.232)$</span>, where:
<span class="math-container">$$L_p(v, c) = \exp((c+o(1))(\log p)^v (\log \log p)^{1-v})$$</span>
It's worth mentioning that this is technically an expected cost, and not an upper bound. This still seems in the spirit of the question to me, but I'll remove it if it's not what you're looking for.</p>

CC BY-SA 4.0
2019-08-26T02:24:01.933Z
Very much in the spirit, thank you!
Rob Simmons
CC BY-SA 4.0
2019-08-13T06:21:27.563Z
2019-08-13T06:21:27.563Z
Mark Schultz-Wu
<p>Recent work of Anupam Gupta, Euiwoong Lee, and Jason Li [1] shows that the Karger-Stein algorithm  for the <a href="https://en.wikipedia.org/wiki/Minimum_k-cut" rel="noreferrer">minimum <span class="math-container">$k$</span>-cut problem</a> has, in fact, asymptotic time complexity <span class="math-container">$O(n^{k+o(1)})$</span>, improving on the original analysis which gave <span class="math-container">$O(n^{2k-2})$</span> (and on previous work by the same authors, which obtained a <em>different</em> algorithm running in time <span class="math-container">$O(n^{1.98k+O(1)})$</span>).</p>

<p>This is likely to be (near)optimal, based on a conditional lower bound of <span class="math-container">$\Omega(n^k)$</span>.</p>

<p><em>Note:</em>  A talk by Jason Li (and the corresponding slides) can be found on the <a href="https://sites.google.com/site/plustcs/past-talks/20191120jasonlicarnegiemellonuniversity" rel="noreferrer">TCS+ website</a>.</p>

<hr>

<p>[1] <em>The Karger—Stein Algorithm is Optimal for <span class="math-container">$k$</span>-cut</em>, Anupam Gupta, Euiwoong Lee, Jason Li. <a href="https://arxiv.org/abs/1911.09165" rel="noreferrer">arXiv:1911.09165</a>, 2019.</p>

CC BY-SA 4.0
2019-12-12T05:27:08.090Z
2019-12-12T15:15:25.333Z
2019-12-12T15:15:25.333Z
Clement C.
<p>The work function algorithm for <span class="math-container">$k$</span>-server was shown to be <span class="math-container">$(2k-1)$</span>-competitive by Koutsoupias and Papadimitriou - the algorithm was known previously and analyzed only in special cases. It is conjectured to be <span class="math-container">$k$</span>-competitive.</p>

CC BY-SA 4.0
2019-08-14T21:32:51.953Z
2024-09-18T15:36:02.880Z
2024-09-18T15:36:02.880Z
Chandra Chekuri
<p>The <span class="math-container">$3$</span>-Hitting Set problem had a few iterations of "better analysis" (see Fernau's papers <a href="https://www.researchgate.net/profile/Henning_Fernau/publication/225911742_A_Top-Down_Approach_to_Search-Trees_Improved_Algorithmics_for_3-Hitting_Set/links/00b7d52da8bba86ff6000000/A-Top-Down-Approach-to-Search-Trees-Improved-Algorithmics-for-3-Hitting-Set.pdf" rel="nofollow noreferrer">[1]</a> <a href="https://eccc.weizmann.ac.il/report/2006/072/" rel="nofollow noreferrer">[2]</a>)
The algorithm before these paper had some arbitrary choices (like 'choose an edge'...), but when the choices are specifically-chosen in a certain way, it allows for a more refined analysis, that is where the improvement comes in. And I think his Appendices in <a href="https://www.researchgate.net/profile/Henning_Fernau/publication/225911742_A_Top-Down_Approach_to_Search-Trees_Improved_Algorithmics_for_3-Hitting_Set/links/00b7d52da8bba86ff6000000/A-Top-Down-Approach-to-Search-Trees-Improved-Algorithmics-for-3-Hitting-Set.pdf" rel="nofollow noreferrer">1</a> give a more refined analysis (counting subproblems/substructures) leading to better recurrences and so better runtimes.
I think there are a number of such examples in the parameterized complexity literature, where adding another variable to the analysis can lead to improved runtimes, but I have been out of that game for several years now and I can't think of specific ones at the moment. There are a number of papers in FPT and PTAS areas that come up when looking for "improved analysis" in the paper titles.</p>

<p>If specifying choices counts as the same algorithm (like union-find's depth-rank heuristic), then the Edmonds-Karp algorithm is an 'improved analysis' of Ford-Fulkerson, and I'd imagine there are plenty of other problems that have algorithms that have seen runtime improvements from new choice rules.</p>

<p>Then there are a whole bunch of amortized analysis of existing algorithms (I think union-find fits under this description, here is another one <a href="https://link.springer.com/article/10.1007/s00453-004-1145-7" rel="nofollow noreferrer">https://link.springer.com/article/10.1007/s00453-004-1145-7</a> ) </p>

CC BY-SA 4.0
2019-08-26T02:28:10.600Z
Making new choices feels close to what I was looking for, but isn't quite there - in a sense, a more-specified algorithm is a "different algorithm" - but these are still very interesting examples!
Rob Simmons
CC BY-SA 4.0
2019-08-13T22:30:51.660Z
2019-08-16T15:36:41.797Z
2019-08-16T15:36:41.797Z
JimN
<p>Are there interesting instances of algorithms that have been published with proven bounds, and where strictly better bounds have later been published? Not better algorithms with better bounds - obviously that's happened! But better analysis leading to a better bound on an existing algorithm</p>

<p>I thought matrix multiplication was an example of this, but I have talked myself out of it (perhaps incorrectly!) after trying to understand Coppersmith–Winograd and its friends better.</p>

CC BY-SA 4.0
2019-08-07T05:43:38.913Z
An ideal example is Matrix Multiplication. Recent improvements are all in fact better analysis (Le Gall, Williams, etc.).
Lwins
CC BY-SA 4.0
2019-08-07T12:11:19.953Z
Lwins - I suspected that might be the case, but skimming some of the papers made me think they were slightly varying both the algorithm and the analysis. I may need to look deeper.
Rob Simmons
CC BY-SA 4.0
2019-08-08T13:24:51.797Z
This is a half-answer, since it's 2nd hand hearsay: when working on determinization of Buechi automata (https://dl.acm.org/citation.cfm?id=1398627), Safra originally analyzed his construction to have a quadratic exponent. Then, after writing the construction down, and due to some misunderstanding, he ended up with the better (optimal) $n\log n$ exponent.
Shaull
CC BY-SA 4.0
2019-08-08T17:09:52.660Z
I would suggest looking into motion planning problems - I feel like there have been several cases there.  Also, IIRC the precise complexity of the simplex algorithm(s?) was a matter of study for quite a while.
Steven Stadnicki
CC BY-SA 4.0
2019-08-13T19:32:43.317Z
Slightly different, but the existence proof of an input satisfying $7m/8$ of the clauses in a 3SAT instance was improved to an explicit algorithm by more careful analysis.
Stella Biderman
CC BY-SA 4.0
2019-08-14T07:26:31.360Z
AKS? I'm not clear as to which reductions in the exponent were due to better analysis and which to better choice of parameters.
Peter Taylor
CC BY-SA 4.0
2019-12-12T17:39:20.810Z
Are you only interested in carefully designed algorithms with complicated initial analyses, or also 'obvious algorithms'/heuristics? For example, hill-climbing local search algorithms are the 'obvious choice' for a lot of problems but often have awful worst case results. But they have been shown to be efficient on certain subclasses of problems (like [our recent result](https://arxiv.org/abs/1907.01218), for example). Or more generally: are you interested in new parameterized complexity results for simple old algorithms but with new kinds of parameters?
Artem Kaznatcheev
CC BY-SA 4.0
2024-09-18T15:37:28.780Z
Does smoothed analysis of the Simplex algorithm count?  https://doi.org/10.1145/990308.990310
Neal Young
<ho.history-overview><analysis-of-algorithms>
When have we found better bounds for known algorithms?
Rob Simmons
# When have we found better bounds for known algorithms?

(Asked by: username_0 on 2019-08-06)

Are there interesting instances of algorithms that have been published with proven bounds, and where strictly better bounds have later been published? Not better algorithms with better bounds - obviously that's happened! But better analysis leading to a better bound on an existing algorithm

I thought matrix multiplication was an example of this, but I have talked myself out of it (perhaps incorrectly!) after trying to understand Coppersmith–Winograd and its friends better.

**Tags:** ho.history-overview, analysis-of-algorithms
> **Comments:**
> **username_1**: An ideal example is Matrix Multiplication. Recent improvements are all in fact better analysis (Le Gall, Williams, etc.).  
> **username_0**: Lwins - I suspected that might be the case, but skimming some of the papers made me think they were slightly varying both the algorithm and the analysis. I may need to look deeper.  
> **username_2**: This is a half-answer, since it's 2nd hand hearsay: when working on determinization of Buechi automata (https://dl.acm.org/citation.cfm?id=1398627), Safra originally analyzed his construction to have a quadratic exponent. Then, after writing the construction down, and due to some misunderstanding, he ended up with the better (optimal) $n\log n$ exponent.  
> **username_3**: I would suggest looking into motion planning problems - I feel like there have been several cases there.  Also, IIRC the precise complexity of the simplex algorithm(s?) was a matter of study for quite a while.  
> **username_4**: Slightly different, but the existence proof of an input satisfying $7m/8$ of the clauses in a 3SAT instance was improved to an explicit algorithm by more careful analysis.  
> **username_5**: AKS? I'm not clear as to which reductions in the exponent were due to better analysis and which to better choice of parameters.  
> **username_6**: Are you only interested in carefully designed algorithms with complicated initial analyses, or also 'obvious algorithms'/heuristics? For example, hill-climbing local search algorithms are the 'obvious choice' for a lot of problems but often have awful worst case results. But they have been shown to be efficient on certain subclasses of problems (like [our recent result](https://arxiv.org/abs/1907.01218), for example). Or more generally: are you interested in new parameterized complexity results for simple old algorithms but with new kinds of parameters?  
> **username_7**: Does smoothed analysis of the Simplex algorithm count?  https://doi.org/10.1145/990308.990310  

---

## 6 answers

### Answer by username_9 on 2019-08-10. Score: 27

The [Union-Find algorithm,](https://en.wikipedia.org/wiki/Disjoint-set_data_structure) which Tarjan1 showed had complexity $n \alpha(n)$, where $\alpha(n)$ is the inverse Ackermann function, had been analyzed previously by several people. According to Wikipedia, it was invented by Galler and Fischer2, but this seems to be incorrect, as they did not have all the components of the algorithm needed to make it run that quickly.

Based on brief scans of the papers, it appears that the algorithm was invented by Hopcroft and Ullman3, who gave an (incorrect) $O(n)$ time bound. Fischer4 then found the mistake in the proof and gave an $O(n \log\log n)$ time bound. Next, Hopcroft and Ullman5 gave an $O(n \log
^\*n)$ time bound, after which Tarjan1 found the (optimal) $O(n \alpha(n))$ time bound.

1 R.E. Tarjan, "Efficiency of a good but not linear set union algorithm" (1975).   
2 B.S. Galler and M.J. Fischer, "An improved equivalence algorithm" (1964).   
3 J.E. Hopcroft and J.D. Ullman, "A linear list merging algorithm" (1971).  
4 M.J. Fischer, "Efficiency of equivalence algorithms" (1972).  
5 J.E. Hopcroft and J.D. Ullman, "Set-merging algorithms" (1973).

> **Comments:**
> **username_10**: The history of this data structure is a little unclear to me and it would be nice to investigate it. I skimmed the Galler and Fischer article, and it seems to describe the Disjoint Sets Forest (DSF) data structure but without the crucial path compression (PC) and weighted union (WU) heuristics. Hopcroft and Ullman attribute DSF with PC and without WU to Tritter, citing Knuth. I am not sure if DSF with both PC and WU was proposed in a published paper prior to Hopcroft and Ullman's paper, although I wouldn't be surprised if it was.  
> **username_9**: @Sasho: This should all be checked, as it's based on brief scans of the papers. Tarjan attributes DSF with both PC and WU to Michael Fischer, in "Efficiency of equivalence algorithms" (1972), which gives an $O(n \log\log n)$ running time for it. Scanning Fischer's paper, he seems to attribute the algorithm to Hopcroft and Ullman in "A linear list merging algorithm", but they give an $\Theta(n)$ running time for it, the proof of which Fischer shows is incorrect. Tarjan says that Hopcroft and Ullman, in "Set-merging algorithms" redeem themselves by giving an $O(n \log^* n)$ bound.  

---

### Answer by username_8 on 2019-08-14. Score: 17

The algorithm of [Paturi, Pudlák, Saks and Zane](https://doi.org/10.1145/1066100.1066101) (PPSZ) for $k\text{-} \mathrm{SAT}$ had been known to have a running time of $O(1.364^n)$ for $3\text{-}\mathrm{SAT}$, with a better bound of $O(1.308^n)$ for formulas guaranteed to have a unique satisfying assignment.
Later [Hertli](https://doi.org/10.1109/FOCS.2011.22) gave an improved analysis showing that this improved run-time bound also holds for the general case, thus showing PPSZ to be the best algorithm for $3\text{-}\mathrm{SAT}$ known at the time.

There is now also a further improved analysis of the algorithm, yielding the bound $O(1.307^n)$ for $3\text{-}\mathrm{SAT}$, due to [Scheder](https://eccc.weizmann.ac.il/report/2021/069/).

> **Comments:**
> **username_0**: This is a really satisfying answer! I think it and the Union Find examples are the best examples of what I was hoping for.  

---

### Answer by username_11 on 2019-08-13. Score: 8

The [Logjam Attack](https://weakdh.org/imperfect-forward-secrecy-ccs15.pdf) mentions that analysis of the general number field sieve (as applied to computing discrete logarithms over $\mathbb{F}\_p$) descent step was tightend, see top left of the 3rd page. As this is the only step that can't be pre-computed (if $\mathbb{F}\_p$ is fixed), its efficiency was instrumental to their attack.

The initial analysis appears to be in [Gordon 92](https://www.dmgordon.org/papers/log.pdf), where descent was costed similarly to precomputation, at $L\_p(1/3, 3^{2/3})$. The tighter analysis seems to be from [Barbulescu's thesis](https://hal.univ-lorraine.fr/tel-01750438), where descent is costed at $L\_p(1/3, 1.232)$, where:
$$L\_p(v, c) = \exp((c+o(1))(\log p)^v (\log \log p)^{1-v})$$
It's worth mentioning that this is technically an expected cost, and not an upper bound. This still seems in the spirit of the question to me, but I'll remove it if it's not what you're looking for.

> **Comments:**
> **username_0**: Very much in the spirit, thank you!  

---

### Answer by username_12 on 2019-12-12. Score: 7

Recent work of Anupam Gupta, Euiwoong Lee, and Jason Li [1] shows that the Karger-Stein algorithm for the [minimum $k$-cut problem](https://en.wikipedia.org/wiki/Minimum_k-cut) has, in fact, asymptotic time complexity $O(n^{k+o(1)})$, improving on the original analysis which gave $O(n^{2k-2})$ (and on previous work by the same authors, which obtained a *different* algorithm running in time $O(n^{1.98k+O(1)})$).

This is likely to be (near)optimal, based on a conditional lower bound of $\Omega(n^k)$.

*Note:* A talk by Jason Li (and the corresponding slides) can be found on the [TCS+ website](https://sites.google.com/site/plustcs/past-talks/20191120jasonlicarnegiemellonuniversity).

---

[1] *The Karger—Stein Algorithm is Optimal for $k$-cut*, Anupam Gupta, Euiwoong Lee, Jason Li. [arXiv:1911.09165](https://arxiv.org/abs/1911.09165), 2019.


---

### Answer by username_13 on 2019-08-14. Score: 6

The work function algorithm for $k$-server was shown to be $(2k-1)$-competitive by Koutsoupias and Papadimitriou - the algorithm was known previously and analyzed only in special cases. It is conjectured to be $k$-competitive.


---

### Answer by username_14 on 2019-08-13. Score: 4

The $3$-Hitting Set problem had a few iterations of "better analysis" (see Fernau's papers [[1]](https://www.researchgate.net/profile/Henning_Fernau/publication/225911742_A_Top-Down_Approach_to_Search-Trees_Improved_Algorithmics_for_3-Hitting_Set/links/00b7d52da8bba86ff6000000/A-Top-Down-Approach-to-Search-Trees-Improved-Algorithmics-for-3-Hitting-Set.pdf) [[2]](https://eccc.weizmann.ac.il/report/2006/072/))
The algorithm before these paper had some arbitrary choices (like 'choose an edge'...), but when the choices are specifically-chosen in a certain way, it allows for a more refined analysis, that is where the improvement comes in. And I think his Appendices in [1](https://www.researchgate.net/profile/Henning_Fernau/publication/225911742_A_Top-Down_Approach_to_Search-Trees_Improved_Algorithmics_for_3-Hitting_Set/links/00b7d52da8bba86ff6000000/A-Top-Down-Approach-to-Search-Trees-Improved-Algorithmics-for-3-Hitting-Set.pdf) give a more refined analysis (counting subproblems/substructures) leading to better recurrences and so better runtimes.
I think there are a number of such examples in the parameterized complexity literature, where adding another variable to the analysis can lead to improved runtimes, but I have been out of that game for several years now and I can't think of specific ones at the moment. There are a number of papers in FPT and PTAS areas that come up when looking for "improved analysis" in the paper titles.

If specifying choices counts as the same algorithm (like union-find's depth-rank heuristic), then the Edmonds-Karp algorithm is an 'improved analysis' of Ford-Fulkerson, and I'd imagine there are plenty of other problems that have algorithms that have seen runtime improvements from new choice rules.

Then there are a whole bunch of amortized analysis of existing algorithms (I think union-find fits under this description, here is another one <https://link.springer.com/article/10.1007/s00453-004-1145-7> )

> **Comments:**
> **username_0**: Making new choices feels close to what I was looking for, but isn't quite there - in a sense, a more-specified algorithm is a "different algorithm" - but these are still very interesting examples!  

---

