haskell/containers — Issue #7: Incorrect complexity documentation for IntMap functions?
Author: mkscrg
Created: 2012-01-29 23:57:50+00:00
State: open

The [haddocks](http://www.haskell.org/ghc/docs/latest/html/libraries/containers-0.4.1.0/Data-IntMap.html#v:findMin) for `IntMap` (including the unreleased `0.5.0.0` version) claim that the runtime complexity of (for example) `findMin` is O(log n). The [implementation](https://github.com/haskell/containers/blob/master/Data/IntMap/Base.hs#L966) looks to me like O(min(W, log n)), since it's just a direct downwards traversal of the tree until a leaf is found. Are the docs wrong or am I missing something?