The complexity of many Haskell collection APIs is actually documented unlike with many other languages. These complexities are not changed by the runtime. Only constant factors and memory use are affected by optimisations and this is no different to any other high-level language that actually optimises code.