A probabilistic analysis of the height of tries and of the complexity of triesort

Summary We consider binary tries formed by using the binary fractional expansions of X₁, ...,X_n, a sequence of independent random variables with common density f on [0,1]. For H_n, the height of the trie, we show that either E(H_n)21og₂n or E(H_n)= for all n2 according to whether f²(x)dx is finite or infinite. Thus, the average height is asymptotically twice the average depth (which is log₂n when f²(x)dx>). The asymptotic distribution of H_n is derived as well.If f is square integrable, then the average number of bit comparisons in triesort is nlog₂n+0(n), and the average number of nodes in the trie is 0(n).Research of the author was supported in part by FCAC Grant EQ-1678