On Fri, Nov 23, 2007 at 09:29:04AM +1300, David Sainty wrote:
> Fair point if the allocation is via malloc(), though it still depends on
> the cost of node comparisons - which may be high in itself.
> 
> But I have a couple of counterpoints :)
> 
> If the node was allocated from a pool then the memory allocation cost
> would be near O(1), as opposed to the (something like) O(lg(n)) cost of
> the initial duplicate check.

The cost of malloc() is much near O(1) these days - since most modern
malloc implementations are 'slab allocators'.

	David

-- 
David Laight: david@l8s.co.uk