Como é avaliada a complexidade temporal da operação de adicionar um elemento ao TreeSet?

Em Java, a classe TreeSet é implementada com base numa árvore vermelho-preto, que é uma árvore binária de pesquisa balanceada. A complexidade temporal da operação de adicionar um elemento ao TreeSet é O(log n), onde n é o número de elementos no conjunto.

Isto deve-se ao facto de, para inserir um elemento, primeiro é procurado na árvore para determinar o local correto, e depois ocorre o balanceamento da árvore, o que leva tempo logarítmico.

Exemplo:

TreeSet<Integer> set = new TreeSet<>();
set.add(10); // O(log n)
set.add(5);  // O(log n)
set.add(20); // O(log n)