Dependence between External Path-Length and Size in Random Tries

Michael Fuchs, Hsien-Kuei Hwang

We study the size and the external path length of random tries and show that they are asymptotically independent in the asymmetric case but strongly dependent with small periodic f…