On Thu, Jul 15, 2010 at 4:30 AM, Stephen Tetley <stephen.tet...@gmail.com> wrote: > 2010/7/15 Jake McArthur <jake.mcart...@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. Cheers! -- Felipe. _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
