Paper Info
Title
Average-Case Analysis of Algorithms Using Kolmogorov Complexity
Abstract
Abstract: Analyzing the average-case complexity of algorithms is a very practical but verydifficult problem in computer science. In the past few years, we have demonstrated thatKolmogorov complexity is an important tool for analyzing the average-case complexityof algorithms. We have developed the incompressibility method [7]. In this paper, weuse several simple examples to further demonstrate the power and simplicity of suchmethod. We prove bounds on the average-case number of stacks (queues)...
Year
DOI
Venue
2000
10.1007/BF02950402
J. Comput. Sci. Technol.
Keywords
DocType
Volume
average-case analysis,sorting,kolmogorov complexity,algorithm
Journal
15
Issue
ISSN
Citations 
5
1860-4749
1
PageRank 
References 
Authors
0.36
3
3
Name
Order
Citations
PageRank
Tao Jiang11809155.32
Ming Li25595829.00
Paul Vitányi32130287.76