OFFSET
0,1
COMMENTS
The saturation level S_n of a binary search tree defined by a random n-permutation is such that S_n/log(n) converges to 0.3733646... in probability.
REFERENCES
Steven R. Finch, Mathematical Constants, Cambridge University Press, 2003, pp. 349-352.
LINKS
Luc Devroye, A Note on the Height of Binary Search Trees. McGill University, Montreal, Canada (1986).
FORMULA
-1/W(-1, -1/(2*e)) where W is the Lambert W function (ProductLog).
EXAMPLE
0.373364617701674084248448436679270595...
MATHEMATICA
RealDigits[-1/ProductLog[-1, -1/(2*E)], 10, 100] // First
CROSSREFS
KEYWORD
nonn,cons
AUTHOR
Jean-François Alcover, May 15 2014
STATUS
approved