Average-case analysis of quicksort and binary insertion tree height using incompressibility

DOI10.1016/j.ipl.2007.01.007zbMath1184.68275OpenAlexW2018207776MaRDI QIDQ2379940

Ming Li, Brendan Lucier, Tao Jiang

Publication date: 24 March 2010

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2007.01.007

zbMATH Keywords

Kolmogorov complexityanalysis of algorithmsincompressibilityquicksortbinary insertion trees

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Cites Work

• Unnamed Item
• Average-case analysis of algorithms using Kolmogorov complexity
• Analyzing variants of Shellsort
• New applications of the incompressibility method. II
• A lower bound on the average-case complexity of shellsort
• A note on the height of binary search trees
• New Applications of the Incompressibility Method

This page was built for publication: Average-case analysis of quicksort and binary insertion tree height using incompressibility