Abstract
We study the joint asymptotic behavior of the space requirement and the total path length (either summing over all root-key distances or over all root-node distances) in random m-ary search trees. The covariance turns out to exhibit a change of asymptotic behavior: it is essentially linear when 3 ≤ m ≤ 13, but becomes of higher order when m ≥ 14. Surprisingly, the corresponding asymptotic correlation coefficient tends to zero when 3 ≤ m ≤ 26, but is periodically oscillating for larger m, and we also prove asymptotic independence when 3 ≤ m ≤ 26. Such a less anticipated phenomenon is not exceptional and our results can be extended in two directions: one for more general shape parameters, and the other for other classes of random log-trees such as fringe-balanced binary search trees and quadtrees. The methods of proof combine asymptotic transfer for the underlying recurrence relations with the contraction method.
Original language | English |
---|---|
Pages (from-to) | 353-379 |
Number of pages | 27 |
Journal | Random Structures and Algorithms |
Volume | 50 |
Issue number | 3 |
DOIs | |
State | Published - 1 May 2017 |
Keywords
- asymptotic analysis
- asymptotic transfer
- contraction method
- correlation
- dependence
- limit law
- m-ary search tree
- recurrence relations