Page 1 Next

Displaying 1 – 20 of 22

Showing per page

Un théorème de finitude

Yvette Amice (1964)

Annales de l'institut Fourier

Démonstration élémentaire de la finitude de l’ensemble de type H associé à une suite de densité uniforme extérieure non nulle.

Uniform distribution modulo one and binary search trees

Michel Dekking, Peter Van der Wal (2002)

Journal de théorie des nombres de Bordeaux

Any sequence x = ( x k ) k = 1 of distinct numbers from [0,1] generates a binary tree by storing the numbers consecutively at the nodes according to a left-right algorithm (or equivalently by sorting the numbers according to the Quicksort algorithm). Let H n ( x ) be the height of the tree generated by x 1 , , x n . Obviously log n log 2 - 1 H n ( x ) n - 1 . If the sequences x are generated by independent random variables having the uniform distribution on [0, 1], then it is well known that there exists c > 0 such that H n ( x ) c log n as n for almost all sequences x . Recently...

Currently displaying 1 – 20 of 22

Page 1 Next