A probabilistic analysis of the height of tries and of the complexity of triesort (Q760797)

We consider binary tries formed by using the binary fractional expansions of \(X_ 1,...,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)\sim 2 \log_ 2 n\) or \(E(H_ n)=\infty\) for all \(n\geq 2\) according to whether \(\int f^ 2(x)dx\) is finite or infinite. Thus, the average height is asymptotically twice the average depth (which is \(\sim \log_ 2 n\) when \(\int f^ 2(x)dx<\infty)\). 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 n log\({}_ 2n+O(n)\), and the average number of nodes in the trie is O(n).