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?