Average-case analysis of algorithms using Kolmogorov complexity

DOI10.1007/BF02950402zbMath0961.68065MaRDI QIDQ1587331

Tao Jiang, Ming Li, Paul M. B. Vitányi

Publication date: 2000

Published in: Journal of Computer Science and Technology (Search for Journal in Brave)

zbMATH Keywords

Kolmogorov complexityaverage-case complexity of algorithms

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Related Items (3)

Average-case analysis of quicksort and binary insertion tree height using incompressibility ⋮ Preimages under the Queuesort algorithm ⋮ Preimages under the bubblesort operator

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Subadditive ergodic theory
• A variational problem for random Young tableaux
• A lower bound on the average-case complexity of shellsort
• Sorting Using Networks of Queues and Stacks

This page was built for publication: Average-case analysis of algorithms using Kolmogorov complexity