So here is some constructive proposal to (hopefully finally) resolve
the problem with the running time guarantees. Instead of listing all
proposed changes, I applied them to the latest draft in John's
repository and you'll find the corresponding patch file attached to
this email.  Please go over the proposed changes.

Besides filling in some running time and size guarantees that were
missing and removing/rewriting some not absolutely correct statements,
the major changes were: Add the notion of an average accessing time,
on which everything else is built. For each procedure returning a
range, the average accessing time is given. Drop the notion of a
vector-style range, which had no clear meaning.

Please ask if you don't understand my rationale behind one or the other thing.

Thanks,

Marc