I recently became very interested in Kolmogorov complexity and the incompressibility method especially in the context of average-case analysis. The "standard" book by Li & Vitanyi showcases many examples, although only two of them are about average-case analysis (heapsort and shellsort). I also found a paper analyzing the average-case of quicksort using incompressibility.

This got me wondering: is there some reason exactly these algorithms were analyzed? More generally, is there something in the nature of an algorithm that makes it suitable (or not at all suitable) for analysis using the incompressibility method?

In addition, does anyone know of any other papers/resources that show even trivial average-analysis of different kind of algorithms, perhaps other than sorting algorithms using the method?


I think that the recent constructive proof of the Lovasz Local Lemma (http://blog.computationalcomplexity.org/2009/06/kolmogorov-complexity-proof-of-lov.html) and Patrascu's analysis of the component size in cuckoo hashing might both qualify. These are both stated in terms of random strings, but would also work with Kolmogorov random strings (http://infoweekly.blogspot.com/2010/02/cuckoo-hashing.html).

  • $\begingroup$ Thanks, seems interesting and exactly what I asked for. I will go through them :) $\endgroup$
    – Juho
    Jun 26 '11 at 15:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.