> in pure FP either lookup or insert can be no better than O(log(n))
For single operations, yes. But what we really care about is usually the amortized performance over many operations, which can still be constant time.
For single operations, yes. But what we really care about is usually the amortized performance over many operations, which can still be constant time.