[Haskell-cafe] trees and pointers

wren ng thornton wren at freegeek.org
Fri Jul 16 00:08:05 EDT 2010


Jake McArthur wrote:
> On 07/15/2010 05:33 PM, Victor Gorokhov wrote:
>>> From the docs, lookup is O(min(n,W))
>> Actually worse than O(log n).
> 
> Perhaps I am misunderstanding you, but O(min(n,W)) is either better than 
> or the same as O(log n), depending on how you look at things, but I 
> don't see any way that the former could be *worse* than the latter.

For n < W: min(n,W) > log n

So, when you can guarantee that n < W ---which is almost always the case 
for IntMap---, then O(min(n,W)) is linear and therefore worse than O(log n).

But even so, if your constant factors are k << c, then k*n < c*log n is 
perfectly possible for all n < W, and therefore what matters in the real 
world here is the constant factors. The reason why is that for 
asymptotic purposes O(min(n,W)) and O(log n) belong to the same class of 
functions between constant and linear, so they're effectively the same 
(in asymptotic-land).

-- 
Live well,
~wren


More information about the Haskell-Cafe mailing list