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

В C# структура данных SortedDictionary реализована на основе красно-черного дерева — сбалансированного бинарного дерева поиска.

Временная сложность операции чтения (поиск элемента по ключу) в SortedDictionary составляет O(log n), где n — количество элементов в словаре.

Это связано с тем, что для поиска элемент обходится по дереву, уменьшая количество проверок в логарифмическое время, в отличие от, например, Dictionary, где поиск — O(1) в среднем, но без упорядочивания ключей.