Asymptotic variance of random symmetric digital search trees

Hsien-Kuei Hwang, Michael Fuchs, Vytas Zacharovas

Asymptotics of the variances of many cost measures in random digital search trees are often notoriously messy and involved to obtain. A new approach is proposed to facilitate such…