FiniteMap performance

[Magnus Lindberg]

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