FiniteMap performance

Hello! I am using the FiniteMap datatype and since Haskell never modifies variables but rather copies them (?) I wonder what the performance of the FiniteMap type is in Haskell. Lookup is of course done in O(log n) but is insertion done in O(n) or O(log n)? For example, does the function addToFM :: Ord key => FiniteMap key elt -> key -> elt -> FiniteMap key elt belong to O(n) or O(log n) (where n is the size of the map) ? If it belongs to O(n), aren't the maps really really useless? If it belongs to O(log n), how is this achieved? (my guess is that it is O(n) of course : ) Best regards, Magnus Lindberg