Partial Match Queries in Random Quadtrees
Hua‐Huai Chern, Hsien‐Kuei Hwang · SIAM Journal on Computing · 2003
We propose a simple direct approach for computing the expected cost of random partial match queries in random quadtrees. This approach gives not only an explicit expression for the leading constant in the asymptotic approximation of the expected cost but also more terms in the asymptotic expansion if desired.