В MSDN указано следующее SortedSet (T).Add Method:
Если Count меньше емкости внутреннего массива, этот метод является операцией O (1).
Разве кто-то может объяснить "как это"? Я хочу сказать, что при добавлении нового значения нам нужно найти правильное место для добавления значения (сравнивая его с другими значениями), а внутренняя реализация выглядит как "красно-черное дерево" с сложностью ввода O (log N).
Комментарий просто неправильный. Да, это красно-черное дерево, O (log (n)) для вставок. Взгляд с Reflector подтверждает это, частный метод AddIfNotPresent() содержит цикл while(), чтобы найти точку вставки, используя обычный черно-белый обход node.
Ошибка этого документа уже была отправлена вами-know-who.