Como é determinada a complexidade temporal da operação de leitura de um elemento da estrutura de dados SortedDictionary?

No C#, a estrutura de dados SortedDictionary é implementada com base numa árvore vermelho-preto, uma árvore binária de pesquisa balanceada.

A complexidade temporal da operação de leitura (pesquisa de elemento por chave) no SortedDictionary é O(log n), onde n é o número de elementos no dicionário.

Isto deve-se ao facto de a pesquisa percorrer a árvore, reduzindo o número de verificações em tempo logarítmico, ao contrário de, por exemplo, Dictionary, onde a pesquisa é O(1) em média, mas sem ordenação das chaves.