Как се определя времевата сложност на операцията за четене на елемент от структурата данни SortedDictionary?

В C#, структурата данни SortedDictionary е реализирана на базата на червено-черно дърво — балансирано двоично дърво за търсене.

Времевата сложност на операцията за четене (търсене на елемент по ключ) в SortedDictionary е O(log n), където n е броят на елементите в речника.

Това се дължи на факта, че търсенето преминава през дървото, намалявайки броя на проверките до логаритмично време, за разлика например от Dictionary, където търсенето е средно O(1), но без сортиране на ключовете.