Correction: Performing O(input) failed insertions into a TreeSet might be O(input log output) runtime, which is slower than what I stated above if input > output.