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