Hogyan határozható meg az olvasási művelet időbeli összetettsége a SortedDictionary adatstruktúrában?

C#-ban a SortedDictionary adatstruktúra egy vörös-fekete fa alapú, kiegyensúlyozott bináris keresőfa.

A SortedDictionary olvasási műveletének (elem keresése kulcs szerint) időkomplexitása O(log n), ahol n a szótárban lévő elemek száma.

Ez abból adódik, hogy a keresés végigjárja a fát, csökkentve a vizsgálatok számát logaritmikus időre, ellentétben például a Dictionary-vel, ahol a keresés átlagosan O(1), de a kulcsok rendezése nélkül.