[Haskell-cafe] trees and pointers

[Jake McArthur]

On 07/15/2010 05:33 PM, Victor Gorokhov wrote:
>
>> Thanks for an example! Probably, one can think about using Arrays
>> instead of Map or IntMap in order to achieve 'true' O(1) in pure. But
>> I suppose that there are some trouble with array expanding. Or
>> somebody would already make it.
>>
> Pure arrays have O(n) modification time.

Excluding DiffArray under certain usage patterns of course, but 
DiffArray is slow for unknown reasons besides algorithmic complexity.

>
>> 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.

- Jake