Abstract
In the analysis of algorithms we are usually interested in obtaining closed form expressions for their complexity, or at least asymptotic expressions in O ( ·)-notation. Unfortunately, there are fundamental reasons why we cannot obtain such expressions from experiments.This paper explains how we can at least come close to this goal using the scientific method. Besides the traditional role of experiments as a source of preliminary ideas for theoretical analysis, experiments can test falsifiable hypotheses obtained by incomplete theoretical analysis. Asymptotic behavior can also be deduced from stronger hypotheses which have been induced from experiments. As long as a complete mathematical analysis is impossible, well tested hypotheses may have to take their place. Several examples for probabilistic problems are given where the average complexity can be well approximated experimentally so that the support for the hypotheses is quite strong. Randomized Shellsort has performance close to O (n log n ); random polling dynamic load balancing between P processors achieves full load sharing in log 2P + O (log log P ) steps; randomized writing to D independent disks using a shared buffer size W achieves average eficiency at least 1 .D/(2W ).
Partially supported by the IST Programme of the EU under contract n mber IST- 1999-14186 (ALCOM-FT).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Y. Azar, A.Z. Broder, A.R. Karlin, and E. Upfal. Balanced allocations. In 26thc ACM Symposium on the Theory of Computing, pages 593–602, 1994.
P. Berenbrink, A. Czumaj, A. Steger, and B. Vöcking. Balanced allocations: The heavily loaded case. In 32th Annual ACM Symposium on Theory of Computing, 2000.
R.D. Blumofe and C.E. Leiserson. Scheduling multithreaded computations by work stealing. In Foundations of Computer Science, pages 356–368, Santa Fe, 1994.
C. Cohen-Tannoudji, B. Diu, and F. Laloë. Quantum Mechanics, volume 2. John Wiley & Sons, Inc., 1977.
A. Goldberg and B. Moret. Combinatorial algorithms test sets (cats). In 10th ACM-SIAM Symposium on Discrete Algorithms, 1999.
J. Hooker. Needed:An empirical science of algorithms. Operations Res., 42(2): 201–212, 1994.
T. Jiang, M. Li, and P. Vitányi. Average-case complexity of shellsort. In ICALP, number 1644 in LNCS, pages 453–462, 1999.
J. Korst. Random duplicate assignment:An alternative to striping in video servers. In ACM Multimedia, pages 2190–226, Seattle, 1997.
V. Kumar, A. Grama, A. Gupta, and G. Karypis. Introduction to Parallel Computing.Design and Analysis of Algorithms.Benjamin/Cummings, 1994.
T. Leighton. Introduction to Parallel Algorithms and Architectures. Morgan Kaufmann, 1992.
M. Matsumoto and T. Nishimura. Mersenne twister: A 623-dimensionally equidistributed uniform pseudo-random n mber generator. ACMTMCS: ACM Transactions on Modeling and Computer Simulation, 8: 3–30, 1998. http://www.math.keio.ac.jp/~matumoto/emt.html.
C. C. McGeoch, D. Precup, and P.R. Cohen. How to find big-oh in your data set (and how not to). In Advances in Intelligent Data Analysis, number 1280 in LNCS, pages 41–52, 1997.
P.H. Müller. Lexikon der Stochastik. Akademie Verlag, 5th edition, 1991.
R. Niedermeier, K. Reinhard, and P. Sanders. Towards optimal locality in meshindexings. In B.S. Chlebus and L. Czaja, editors, Fundamentals of Computation Theory, number 1279 in LNCS, pages 364–375, Krakow, 1997.
K.R. Popper. Logik der Forschung. Springer, 1934. English Translation: The Logic of Scientific Discovery, Hutchinson, 1959.
W.H. Press, S. Teukolsky, W.T. Vetterling, and B.P. Flannery. Numerical Recipes in C. Cambridge University Press, 2.edition, 1992.
P. Sanders. Lastverteilungsalgorithmen für parallele Tiefensuche. Number 463 in Fortschrittsberichte, Reihe 10.VDI Verlag, 1997.
P. Sanders, S. Egner, and J. Korst. Fast concurrent access to parallel disks. In 11th ACM-SIAM Symposium on Discrete Algorithms, pages 849–858, 2000.
R. Sedgewick. Analysis of shellsort and related algorithms. LNCS, 1136: 1–11, 1996.
D.L. Shell. A high-speed sorting procedure.Communications of the ACM, 2(7): 30–33, July 1958.
B. Vöcking. How asymmetry helps load balancing. In 40th FOCS, pages 131–140, 1999.
M.A. Weiss. Empirical study of the expected running time of shellsort. The Computer Journal, 34(1): 88–91, 1991.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2001 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Sanders, P., Fleischer, R. (2001). Asymptotic Complexity from Experiments? A Case Study for Randomized Algorithms. In: Näher, S., Wagner, D. (eds) Algorithm Engineering. WAE 2000. Lecture Notes in Computer Science, vol 1982. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-44691-5_12
Download citation
DOI: https://doi.org/10.1007/3-540-44691-5_12
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-42512-0
Online ISBN: 978-3-540-44691-0
eBook Packages: Springer Book Archive