Average-Case Analysis Using Kolmogorov Complexity

Ming Li () and Paul Vitányi ()
Additional contact information
Ming Li: City University of Hong Kong
Paul Vitányi: CWI and University of Amsterdam

A chapter in Advances in Algorithms, Languages, and Complexity, 1997, pp 157-169 from Springer

Abstract: Abstract This expository paper demonstrates how to use Kolmogorov complexity to do the average-case analysis via four examples, and exhibits a surprising property of the celebrated associated universal distribution. The four examples are: average case analysis of Heapsort [17, 15], average nni-distance between two binary rooted leave-labeled trees [20], compact routing in computer networks [3], average-case analysis of an adder algorithm [4]. The property is that the average-case complexity of any algorithm whatsoever equals its worst-case complexity if the inputs are distributed according to the Universal Distribution [14]. We provide the proofs for the latter three items.

Keywords: Random Graph; Kolmogorov Complexity; Longe Common Subsequence; Universal Distribution; Average Case Analysis (search for similar items in EconPapers)
Date: 1997
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-1-4613-3394-4_7

Ordering information: This item can be ordered from
http://www.springer.com/9781461333944

DOI: 10.1007/978-1-4613-3394-4_7

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().