3 ms·
> 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 perform
by hither_shores 4y ago
> 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.
- misja111 4y agoNo, this is not the case. It is actually for non FP solutions that the amortized performance converges to constant time. But for pure FP, there is no solution that performs in constant time, also not when amortized.