Come viene determinata la complessità temporale dell'operazione di lettura di un elemento dalla struttura dati SortedDictionary?

In C#, la struttura dati SortedDictionary è implementata su un albero rosso-nero, un albero binario di ricerca bilanciato.

La complessità temporale dell'operazione di lettura (ricerca di un elemento tramite la chiave) in SortedDictionary è O(log n), dove n è il numero di elementi nel dizionario.

Ciò è dovuto al fatto che la ricerca attraversa l'albero, riducendo il numero di verifiche in tempo logaritmico, a differenza di, ad esempio, Dictionary, dove la ricerca è in media O(1), ma senza ordinare le chiavi.