{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,4]],"date-time":"2025-07-04T21:01:02Z","timestamp":1751662862835,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540425120"},{"type":"electronic","value":"9783540446910"}],"license":[{"start":{"date-parts":[[2001,1,1]],"date-time":"2001-01-01T00:00:00Z","timestamp":978307200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2001]]},"DOI":"10.1007\/3-540-44691-5_12","type":"book-chapter","created":{"date-parts":[[2007,6,2]],"date-time":"2007-06-02T22:32:07Z","timestamp":1180823527000},"page":"135-146","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Asymptotic Complexity from Experiments? A Case Study for Randomized Algorithms"],"prefix":"10.1007","author":[{"given":"Peter","family":"Sanders","sequence":"first","affiliation":[]},{"given":"Rudolf","family":"Fleischer","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2001,8,24]]},"reference":[{"key":"12_CR1","doi-asserted-by":"crossref","unstructured":"Y. Azar, A.Z. Broder, A.R. Karlin, and E. Upfal. Balanced allocations. In 26thc ACM Symposium on the Theory of Computing, pages 593\u2013602, 1994.","DOI":"10.1145\/195058.195412"},{"key":"12_CR2","doi-asserted-by":"crossref","unstructured":"P. Berenbrink, A. Czumaj, A. Steger, and B. V\u00f6cking. Balanced allocations: The heavily loaded case. In 32th Annual ACM Symposium on Theory of Computing, 2000.","DOI":"10.1145\/335305.335411"},{"key":"12_CR3","doi-asserted-by":"crossref","unstructured":"R.D. Blumofe and C.E. Leiserson. Scheduling multithreaded computations by work stealing. In Foundations of Computer Science, pages 356\u2013368, Santa Fe, 1994.","DOI":"10.1109\/SFCS.1994.365680"},{"key":"12_CR4","unstructured":"C. Cohen-Tannoudji, B. Diu, and F. Lalo\u00eb. Quantum Mechanics, volume 2. John Wiley & Sons, Inc., 1977."},{"key":"12_CR5","unstructured":"A. Goldberg and B. Moret. Combinatorial algorithms test sets (cats). In 10th ACM-SIAM Symposium on Discrete Algorithms, 1999."},{"issue":"2","key":"12_CR6","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1287\/opre.42.2.201","volume":"42","author":"J. Hooker","year":"1994","unstructured":"J. Hooker. Needed:An empirical science of algorithms. Operations Res., 42(2): 201\u2013212, 1994.","journal-title":"Operations Res."},{"key":"12_CR7","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"453","DOI":"10.1007\/3-540-48523-6_42","volume-title":"ICALP","author":"T. Jiang","year":"1999","unstructured":"T. Jiang, M. Li, and P. Vit\u00e1nyi. Average-case complexity of shellsort. In ICALP, number 1644 in LNCS, pages 453\u2013462, 1999."},{"key":"12_CR8","doi-asserted-by":"crossref","unstructured":"J. Korst. Random duplicate assignment:An alternative to striping in video servers. In ACM Multimedia, pages 2190\u2013226, Seattle, 1997.","DOI":"10.1145\/266180.266372"},{"key":"12_CR9","unstructured":"V. Kumar, A. Grama, A. Gupta, and G. Karypis. Introduction to Parallel Computing.Design and Analysis of Algorithms.Benjamin\/Cummings, 1994."},{"key":"12_CR10","unstructured":"T. Leighton. Introduction to Parallel Algorithms and Architectures. Morgan Kaufmann, 1992."},{"key":"12_CR11","first-page":"3","volume":"8","author":"M. Matsumoto","year":"1998","unstructured":"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\u201330, 1998. http:\/\/www.math.keio.ac.jp\/~matumoto\/emt.html .","journal-title":"ACMTMCS: ACM Transactions on Modeling and Computer Simulation"},{"key":"12_CR12","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1007\/BFb0052828","volume-title":"Advances in Intelligent Data Analysis","author":"C. C. McGeoch","year":"1997","unstructured":"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\u201352, 1997."},{"key":"12_CR13","unstructured":"P.H. M\u00fcller. Lexikon der Stochastik. Akademie Verlag, 5th edition, 1991."},{"key":"12_CR14","series-title":"Lect Notes Comput Sci","doi-asserted-by":"publisher","first-page":"364","DOI":"10.1007\/BFb0036198","volume-title":"Fundamentals of Computation Theory","author":"R. Niedermeier","year":"1997","unstructured":"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\u2013375, Krakow, 1997."},{"key":"12_CR15","unstructured":"K.R. Popper. Logik der Forschung. Springer, 1934. English Translation: The Logic of Scientific Discovery, Hutchinson, 1959."},{"key":"12_CR16","unstructured":"W.H. Press, S. Teukolsky, W.T. Vetterling, and B.P. Flannery. Numerical Recipes in C. Cambridge University Press, 2.edition, 1992."},{"key":"12_CR17","unstructured":"P. Sanders. Lastverteilungsalgorithmen f\u00fcr parallele Tiefensuche. Number 463 in Fortschrittsberichte, Reihe 10.VDI Verlag, 1997."},{"key":"12_CR18","unstructured":"P. Sanders, S. Egner, and J. Korst. Fast concurrent access to parallel disks. In 11th ACM-SIAM Symposium on Discrete Algorithms, pages 849\u2013858, 2000."},{"key":"12_CR19","series-title":"Lect Notes Comput Sci","first-page":"1","volume-title":"Analysis of shellsort and related algorithms","author":"R. Sedgewick","year":"1996","unstructured":"R. Sedgewick. Analysis of shellsort and related algorithms. LNCS, 1136: 1\u201311, 1996."},{"issue":"7","key":"12_CR20","doi-asserted-by":"publisher","first-page":"30","DOI":"10.1145\/368370.368387","volume":"2","author":"D.L. Shell","year":"1958","unstructured":"D.L. Shell. A high-speed sorting procedure.Communications of the ACM, 2(7): 30\u201333, July 1958.","journal-title":"Communications of the ACM"},{"key":"12_CR21","doi-asserted-by":"crossref","unstructured":"B. V\u00f6cking. How asymmetry helps load balancing. In 40th FOCS, pages 131\u2013140, 1999.","DOI":"10.1109\/SFFCS.1999.814585"},{"issue":"1","key":"12_CR22","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1093\/comjnl\/34.1.88","volume":"34","author":"M.A. Weiss","year":"1991","unstructured":"M.A. Weiss. Empirical study of the expected running time of shellsort. The Computer Journal, 34(1): 88\u201391, 1991.","journal-title":"The Computer Journal"}],"container-title":["Lecture Notes in Computer Science","Algorithm Engineering"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-44691-5_12","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,16]],"date-time":"2025-01-16T21:47:36Z","timestamp":1737064056000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44691-5_12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001]]},"ISBN":["9783540425120","9783540446910"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/3-540-44691-5_12","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2001]]},"assertion":[{"value":"24 August 2001","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}