Jak je určena časová složitost operace čtení prvku ze struktury SortedDictionary?

V C#, datová struktura SortedDictionary je implementována na základě červené-černé stromu, vyváženého binárního vyhledávacího stromu.

Časová složitost operace čtení (vyhledávání prvku podle klíče) v SortedDictionary je O(log n), kde n je počet prvků ve slovníku.

To je způsobeno tím, že vyhledávání prochází strom, snižujíc počet kontrol na logaritmický čas, na rozdíl od například Dictionary, kde je hledání průměrně O(1), ale bez řazení klíčů.