On 1/31/2012 7:49 AM, Kevin Wampler wrote:
>
> Although I haven't done it myself, I believe if you actually do the
> complexity analysis you'll find that the lack of random access doesn't
> change the complexity of the obvious recursive algorithm except by a
> constant factor.

Ok, I actually looked at it and the obvious algorithm does take O(n 
log(n)) on a linked list.  But you I think you can modify it prettily 
easily to run in O(n) by treating the linked list as a list of trees of 
size 1, and iteratively running through the list and forming larger 
trees from the smaller ones.  There's probably some fiddily details to 
get balancing just right while ensuring combining the sub-trees takes 
O(1) though, but I think it'll all work out.

Post a reply to this message