patternMinor
Analytic combinatorics and less-precise running times
Viewed 0 times
analyticcombinatoricsrunninglesstimesandprecise
Problem
Analytic combinatorics and concrete mathematics are the mathematics of asymptotic counting, and they draw from combinatorics, analysis, and probability. These techniques have been applied to the analysis of algorithms, e.g. in books by Knuth and (his student) Sedgewick. However, the results tend to be very precise -- they might give a running time as $c n \log(n) + O(n \log(n)^2)$ for example. Running times in Introduction to Algorithms on the other hand generally require simpler math are more likely to be stated as $\Theta(n \log(n))$. My question is whether there are examples where the advanced mathematics of analytic combinatorics is necessary even to get a rough Big-Theta running time.
After all, a commonly-applied version of singularity analysis is a statement about Big-Oh bounds:
This is from chapter 13 of Selected Papers on Analysis of Algorithms:
In chapter 26 Knuth uses complex analysis to find that "the average carry propagation time to add n-place numbers" is
Whereas in Introduction to Algorithms we find this:
After all, a commonly-applied version of singularity analysis is a statement about Big-Oh bounds:
This is from chapter 13 of Selected Papers on Analysis of Algorithms:
In chapter 26 Knuth uses complex analysis to find that "the average carry propagation time to add n-place numbers" is
Whereas in Introduction to Algorithms we find this:
Solution
The analysis of Heapsort's average case time does not yield the constants involved. This is a fundamental issue with algorithms of this nature relying on dynamic updates. The analysis, establishing the optimality of heapsort's average-case time, inevitably proceeds by contradiction for instance using a Kolomogorov complexity incompressibility argument. The reason is that the precise analysis of the selection phase cannot be done by standard means and remained an open problem. The problem is inherent in all heapsort variants to date with one more recent exception (Percolating Heasport).
Heapsort provides the requested example where more advanced techniques are required to obtain $\Theta(n \log(n))$. Note that Sedgewick and Schaffer's original work go the analytic route is still by contradiction (involving a longer argument than the incompressibility method) and facing the same issues.
The following references contain the relevant material
-
Sedgewick, Schaffer, The analysis of Heapsort
-
Li and Vitanyi "An Introduction to Kolmogorov Complexity and Its Applications" discusses the incompressibility argument for Heapsort.
-
Knuth, TAOCP, Vol III (Sorting and Searching), discusses the open problem on the selection phase.
-
Schellekens, A Modular Calculus for the Average Cost of Data Structuring discusses the history and root of the problem and the alternative of Percolating Heapsort.
Heapsort provides the requested example where more advanced techniques are required to obtain $\Theta(n \log(n))$. Note that Sedgewick and Schaffer's original work go the analytic route is still by contradiction (involving a longer argument than the incompressibility method) and facing the same issues.
The following references contain the relevant material
-
Sedgewick, Schaffer, The analysis of Heapsort
-
Li and Vitanyi "An Introduction to Kolmogorov Complexity and Its Applications" discusses the incompressibility argument for Heapsort.
-
Knuth, TAOCP, Vol III (Sorting and Searching), discusses the open problem on the selection phase.
-
Schellekens, A Modular Calculus for the Average Cost of Data Structuring discusses the history and root of the problem and the alternative of Percolating Heapsort.
Context
StackExchange Computer Science Q#149180, answer score: 2
Revisions (0)
No revisions yet.