josef.svenningsson at gmail.com
Tue Apr 4 18:48:17 EDT 2006
On 4/4/06, Ross Paterson <ross at soi.city.ac.uk> wrote:
> On Tue, Apr 04, 2006 at 09:27:56PM +0200, Josef Svenningsson wrote:
> > On 3/31/06, Ross Paterson <ross at soi.city.ac.uk> wrote:
> > > On Thu, Mar 30, 2006 at 04:08:23PM -0500, Jim Apple wrote:
> > > > Ok, so, let my try once more:
> > > >
> > > > Are there any operations f such that f . reverse has a worse big-O
> > > > time bound than f does alone?
> > >
> > > The big-O will be the same in all cases, but the constant factor will
> > > be a little larger, because reverse does a constant amount of work on
> > > each node, if that node is demanded.
> > >
> > This seemed very mysterious to me at first. It seemed to imply that
> > one couldn't observe the linear behaviour of reverse. In fact it
> > seemed like in any program that we could write, any call to reverse
> > would only contribute a constant amount of work. After discussing this
> > with NilsAnders Danielsson and Ulf Norell today we came up with the
> > following program:
> > index i . reverse . reverse .... reverse
> > where you compose reverse k times.
> > Now, if reverse were really constant time then it would have
> > complexity O(k) + O(log(min(i,n-i))). But when we actually try took
> > look up one element we must perform k reversals at each level in the
> > finger tree. Each reversal is a constant amount of work since we won't
> > force anything else but the thunks in path to the index we're
> > interested in. This gives that the actual complexity of the above
> > program is O(k log(min(i,n-i))). So reverse is costlier than a
> > constant factor but it still seems difficult to write a program which
> > demonstrates the claimed linearity of the reverse operation(*).
> I think that's consistent with what I said: reverse increases the
> constant factor; k reverses increase it k times. The constant amount
> of work is at each node, not in the structure overall. The increase is
> approximately the constant amount of work done at each node. index i
> visits O(log(min(i,n-i))) nodes, forcing each of the k reverses on each
> of those nodes.
Oh, I didn't mean to suggest that what you said was wrong. What I was
trying to say was that I initially misinterpreted your statement and
thought that it implied that reverse was a constant time operation.
Our analysis is indeed consistent with what you said. And I'm happy to
hear that you agree with our reasoning.
All the best,
More information about the Libraries