Content deleted Content added
illo |
→Applications: Add BST lower bounds |
||
Line 56:
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. <ref>{{citation
| last1 = Wilber | first1 = Robert
| contribution = Lower Bounds for Accessing Binary Search Trees With Rotations
| doi = 10.1109/SFCS.1986.28
| pages = 61-70
| title = 27th Annual Symposium on Foundations of Computer Science (sfcs 1986)
| contribution-url = https://ieeexplore.ieee.org/abstract/document/4568196
| year = 1989| title-link = Symposium on Foundations of Computer Science
| isbn = 0-8186-0740-8
}}.</ref>
In musical studies, the bit-reversal permutation has also been used to correlate ranking functions of metric weight and classical-corpus onset frequencies in a common-time (4/4) measure.<ref>{{citation
| |||