I wonder why are (time and space asymptotic) complexity guarantees so sparse in the Java API.
Today I was trying to write some code that preprocesses an AST and then can quickly answer the query: "Give me the set of variables that are read/written by the piece of code represented by this AST node." There are many ways to implement this thing but one natural one is to associate a persistent set of variables to each AST node during preprocessing. [Edit: This sentence is wrong. See comments.] Combining two sets takes logarithmic time so preprocessing is done in linear time. There is also going to be a lot of memory sharing. Now, how to do that in Java? The first approximation that came to mind was to use
TreeSet.addAll. That will obviously be much worse but... how much worse? The API documentation gives no clue about the complexity of
TreeSet.addAll so I had to look at the SDK code to see that it is O(n lg n). I proceeded to implement a custom data structure.