[Haskell-cafe] trees and pointers

[wren ng thornton]

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