[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
More information about the Haskell-Cafe