{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,3]],"date-time":"2025-11-03T13:24:23Z","timestamp":1762176263579},"reference-count":10,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2000,9,1]],"date-time":"2000-09-01T00:00:00Z","timestamp":967766400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. Comput. Sci. &amp; Technol."],"published-print":{"date-parts":[[2000,9]]},"DOI":"10.1007\/bf02950402","type":"journal-article","created":{"date-parts":[[2008,9,13]],"date-time":"2008-09-13T14:02:55Z","timestamp":1221314575000},"page":"402-408","source":"Crossref","is-referenced-by-count":6,"title":["Average-case analysis of algorithms using Kolmogorov complexity"],"prefix":"10.1007","volume":"15","author":[{"given":"Tao","family":"Jiang","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ming","family":"Li","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Paul M. B.","family":"Vit\u00e1nyi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"BF02950402_CR1","unstructured":"Knuth D. E. The Art of Computer Programming. Vol.3: Sorting and Searching, Addison-Wesley, 1973 (1st Edition), 1998 (2nd Edition)."},{"key":"BF02950402_CR2","doi-asserted-by":"crossref","first-page":"341","DOI":"10.1145\/321694.321704","volume":"19","author":"R E Tarjan","year":"1972","unstructured":"Tarjan R E. Sorting using networks of queues and stacks.Journal of the ACM, 1972, 19: 341\u2013346.","journal-title":"Journal of the ACM"},{"key":"BF02950402_CR3","unstructured":"Jiang T, Li M, Vit\u00e1nyi P. A lower bound on the average-case complexity of Shellsort.J. Assoc. Comp. Mach., to appear. Also inICALP\u201999, July 11\u201315, 1999, Prague."},{"key":"BF02950402_CR4","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4757-2606-0","volume-title":"An Introduction to Kolmogorov Complexity and Its Applications","author":"M Li","year":"1997","unstructured":"Li M, Vit\u00e1nyi P M B. An Introduction to Kolmogorov Complexity and Its Applications. Springer-Verlag, New York, 2nd Edition, 1997.","edition":"2nd Edition"},{"key":"BF02950402_CR5","unstructured":"Buhrman H, Jiang T, Li M, Vit\u00e1nyi P. New applications of the incompressibility method. InICALP\u201999, July 11\u201315, 1999, Prague. Also inTheoretical Computer Science, 1999, 235."},{"issue":"1","key":"BF02950402_CR6","first-page":"1","volume":"1","author":"A N Kolmogorov","year":"1965","unstructured":"Kolmogorov A N. Three approaches to the quantitative definition of information.Problems Inform. Transmission, 1965, 1(1): 1\u20137.","journal-title":"Problems Inform. Transmission"},{"key":"BF02950402_CR7","first-page":"527","volume":"18","author":"S V Kerov","year":"1977","unstructured":"Kerov S V, Versik A M. Asymptotics of the Plancherel measure on symmetric group and the limiting form of the Young tableaux.Soviet Math. Dokl., 1977, 18: 527\u2013531.","journal-title":"Soviet Math. Dokl."},{"key":"BF02950402_CR8","doi-asserted-by":"crossref","first-page":"883","DOI":"10.1214\/aop\/1176996798","volume":"1","author":"J F C Kingman","year":"1973","unstructured":"Kingman J F C. The ergodic theory of subadditive stochastic processes.Ann. Probab., 1973, 1: 883\u2013909.","journal-title":"Ann. Probab."},{"key":"BF02950402_CR9","doi-asserted-by":"crossref","first-page":"206","DOI":"10.1016\/0001-8708(77)90030-5","volume":"26","author":"B F Logan","year":"1977","unstructured":"Logan B F, Shepp L A. A variational problem for random Young tableaux.Advances in Math., 1977, 26: 206\u2013222.","journal-title":"Advances in Math."},{"issue":"7","key":"BF02950402_CR10","doi-asserted-by":"crossref","first-page":"30","DOI":"10.1145\/368370.368387","volume":"2","author":"D L Shell","year":"1959","unstructured":"Shell D L. A high-speed sorting procedure.Commun. ACM, 1959, 2(7): 30\u201332.","journal-title":"Commun. ACM"}],"container-title":["Journal of Computer Science and Technology"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02950402.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF02950402\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02950402","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,21]],"date-time":"2019-05-21T16:36:04Z","timestamp":1558456564000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF02950402"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000,9]]},"references-count":10,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2000,9]]}},"alternative-id":["BF02950402"],"URL":"https:\/\/doi.org\/10.1007\/bf02950402","relation":{},"ISSN":["1000-9000","1860-4749"],"issn-type":[{"value":"1000-9000","type":"print"},{"value":"1860-4749","type":"electronic"}],"subject":[],"published":{"date-parts":[[2000,9]]}}}