4

According to Wikipedia, there are two common measures of time-complexity of algorithms: the more common worst-case complexity and the less common average-case complexity.

Question 1

Assume that average-case complexity gives the expected value of run time for given input length $n$. What about the standard deviation which would also be an important and interesting number? Is it considered and compared in the literature? Or is the calculation or estimation of the standard deviation not feasible, in general? Or just not interesting or useful (to know)?

Question 2

I wonder whether the following measure of time-complexity has been considered and defined and how it is called. The idea behind this measure is to ask how large in the average the difference is between the true result for an input and the temporary result after $n$ iteration steps. It is assumed

  • that such a difference is defined,
  • that the result is calculated iteratively, and
  • that after each step there is a definite temporary result which can sensibly be given as an approximate result.
Community
  • 1
Hans-Peter Stricker
  • 18,159

1 Answers1

1

It is already time to write an answer, but I hope later to expand it a little.

Answer 2 for the worst-case approximation instead of the average-case that

First of all, we may directly use convergence rates from analysis, defined for sequences and series.

More complexity theory related approximation measure is polynomial-time approximation scheme and its variants.

Investigation of approximability of new problem solution it a typical quest in complexity theory. For instance, an approximation of a chromatic number of a graph with $n$ vertices within a factor of $O(n^{1-\varepsilon})$, for any $\varepsilon> 0$, is NP-hard. [Zuc] Known for me, recent examples can be found, for instance in [MRR, beginning], [CDRS, Section 1], [AT, “Related work”],[BDT, “Variants and generalizations].

References

[AT] Adrian Dumitrescu, Csaba D. Tóth. Packing anchored rectangles.

[BDT] Kevin Balas, Adrian Dumitrescu, Csaba D. Tóth. Anchored Rectangle and Square Packings.

[CDRS] Steven Chaplick, Minati De, Alexander Ravsky, Joachim Spoerhase. Approximation Schemes for Geometric Coverage Problems.

[MRR] Nabil H. Mustafa, Rajiv Raman, and Saurabh Ray. Quasi-polynomial time approximation scheme for weighted geometric set cover on pseudodisks and halfspaces. SIAM J. Comput., 44(1):1650–1669, 2015.

[Zuc] David Zuckerman. Linear degree extractors and the inapproximability of max clique and chromatic number. Theory Comput., 3(1):103-128, 2007. doi:10.4086/toc. 2007.v003a006.

Alex Ravsky
  • 90,434