Dependence and phase changes in random m-ary search trees

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.