[Haskell-cafe] trees and pointers

Felipe Lessa felipe.lessa at gmail.com
Thu Jul 15 03:34:26 EDT 2010

On Thu, Jul 15, 2010 at 4:30 AM, Stephen Tetley
<stephen.tetley at gmail.com> wrote:
> 2010/7/15 Jake McArthur <jake.mcarthur at gmail.com>:
>> On 07/14/2010 05:01 PM, Victor Gorokhov wrote:
>>> You can implement pure pointers on top of Data.Map with O(log n) time
>> Or on top of Data.IntMap with O(1) time. ;)
> Unlikely...
> >From the docs, lookup is O(min(n,W))

W is a constant, 32 or 64 on most machines, so this is really O(W) = O(1).

Should someone create an IntegerMap, then lookup wouldn't be O(1) as W
would be variable.



More information about the Haskell-Cafe mailing list