Application of basic hypergeometric series.
The study of the average search costs in a digital search tree built from \(n\) random data relies on the explicit expression of the polynomial \(H_{n}(u)\), of degree \(n\) in \(u\), which has as the coefficient of \(u^{k}\) the expected number of nodes on this level. Using some results from the theory of \(q\)-hypergeometric functions the authors derive this explicit formula. Some background material from the theory of basic hypergeometric functions is also provided.
scientific article; zbMATH DE number 2032658