On Sun, Mar 26, 2006 at 06:35:14PM -0500, Jim Apple wrote: > On 3/26/06, Ross Paterson <ross at soi.city.ac.uk> wrote: > > the cost of reverse can only be observed by traversing the whole sequence. > > So, head . reverse is . . . O(1)? Certainly. The middle subtree, containing all but 2 to 8 of the elements, is unused.