Re: Fast Sequences

On Thu, Mar 30, 2006 at 04:08:23PM -0500, Jim Apple wrote:

On 3/27/06, Ross Paterson wrote:

...

On Sun, Mar 26, 2006 at 10:54:59PM -0500, Jim Apple wrote:

...

How about

(flip index i) . reverse

Is that O(i)?

index i is O(log(min(i,n-i))), because the index operation skips many subtrees on the way. This skipping will also mean that putting a reverse first won't change the big-O complexity.

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.