30 Mar
2006
30 Mar
'06
4:08 p.m.
On 3/27/06, Ross Paterson
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? Jim