Most lookup operations, and most “point update” operations (which update a single element or pair), have O(log n) time complexity. In these cases, n refers to the size of the collection.
FSet has several operations, such as union on sets, that combine two collections. These
operations are normally O(n), but there are two exceptions. On one hand, if the collections are
not of the same type and organization, more generic methods are invoked that are O(n log n).
On the other, under some circumstances (when they are of the same type and organization), they can
take O(log n) time. The latter occurs if they are historically related: one is the result
of making a small number of point updates on the 6other, or they are both the result of making such
updates on a common ancestor. Under such circumstances, their internal trees will be largely
shared; the implementations detect and exploit this sharing to elide most of the work.
Also, even when these operations do take O(n) time, there’s the question of exactly what n corresponds to. For many of these operations, in the worst case, it’s the sum of the two sizes, but in typical cases it’s often closer to the minimum of the two. For some operations, notably intersection (including map and bag intersection and bag product), it’s the minimum even in the worst case. For asymmetrical operations like set-difference, it’s the size of the left operand.