Duality of upper and lower bounds

The idea that a good lower bound should be a natural dual of the best upper bound is an important point of this thesis.A balanced binary search tree with the array A 1…n in its leaves is the standard upper bound for the partial- sums problem.To store the sum of all leaves in its subtree every internal node is improved.An update calculates all values on the leaf-to-root path but a query sums left children dangling from the root-to-leaf path.

It can be asked when an update (a cell write) to some node v is actually useful while thinking from a lower bound aspect.The value v stores is used for any query that lies in the subtree of its right sibling, if v is a left child.If a query to the sibling’s subtree occurs before another update recomputes v’s value, a write to v is useful.Particularly, whenever there is an interleave between v’s left and right subtrees sorting operations by time, a write instruction is useful, see figure

1.4 .

Apparently, the sum of the interleaves at every node of the binary search tree is the amount of “useful work” that the algorithm does.I use a bit-reversal permutation again, to maximize this sum.Notably the permutation is invariant under 90-degree rotations; in other words the bit-reversal permutation is equal to its own inverse (reversing the bits twice gives the identity).So, the lower-bound tree lying on the time axis counts exactly the same interleaves that generate work in the upper bound.