Kaip nustatoma laiko sudėtingumas skaitant elementą iš SortedDictionary duomenų struktūros?

C# kalboje, SortedDictionary duomenų struktūra įgyvendinta remiantis raudonojo-juodojo medžio — subalansuoto dvejetainio paieškos medžio.

SortedDictionary skaitymo operacijos (elemento paieška pagal raktą) laiko sudėtingumas yra O(log n), kur n yra žodyno elementų skaičius.

Tai susiję su tuo, kad paieška eina per medį ir sumažina patikrinimų skaičių iki logaritminio laiko, skirtingai nuo, pavyzdžiui, Dictionary, kur paieška vidutiniškai yra O(1), bet be raktų rūšiavimo.