Content deleted Content added
→Algorithms: + |
→Applications: −sp |
||
Line 73:
The [[Van der Corput sequence]], a [[low-discrepancy sequence]] of numbers in the [[unit interval]], is formed by reinterpreting the indexes of the bit-reversal permutation as the [[Fixed-point arithmetic|fixed-point binary representations]] of [[dyadic rational number]]s.
Bit-reversal permutations are often used in finding lower bounds on dynamic [[data structures]]. For example, subject to certain assumptions, the cost of looking up the integers between <math>0</math> and <math>n-1</math>, inclusive, in any [[binary search tree]] holding those values, is <math>\Omega(n \log n)</math> when those numbers are queried in bit-reversed order. This bound applies even to trees like [[splay trees]] that are allowed to rearrange their nodes between accesses.
| last1 = Wilber | first1 = Robert
| contribution = Lower Bounds for Accessing Binary Search Trees With Rotations
| |||