jbapple+haskell-lib at gmail.com
Thu Mar 30 16:08:23 EST 2006
On 3/27/06, Ross Paterson <ross at soi.city.ac.uk> 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?
More information about the Libraries