Hoe wordt de tijdcomplexiteit van de bewerking om een element uit de SortedDictionary-gegevensstructuur te lezen bepaald?

In C# is de datastructuur SortedDictionary geïmplementeerd op basis van een rood-zwart boom, een gebalanceerde binaire zoekboom.

De tijdcomplexiteit van de leesoperatie (zoek naar een element op basis van de sleutel) in SortedDictionary is O(log n), waarbij n het aantal elementen in het woordenboek is.

Dit komt doordat de zoekopdracht door de boom loopt en het aantal controles in logaritmische tijd vermindert, in tegenstelling tot bijvoorbeeld Dictionary, waar de zoekopdracht gemiddeld O(1) is, maar zonder sortering van de sleutels.