Добавить в SortedSet <T>и его сложность

Question

MSDN сообщает следующее SortedSet (T). Добавить метод :

Если число меньше емкости внутреннего массива, этот метод является операцией O (1).

Может кто-нибудь объяснить, "как это так"? Я имею в виду, что при добавлении нового значения нам нужно найти правильное место для добавления значения (сравнивая его с другими значениями), а внутренняя реализация выглядит как «красно-черное дерево» со сложностью вставки O (log N).

Answer 1

Комментарий просто неправильный. Да, это красно-черное дерево, O (log (n)) для вставок. Если взглянуть на Reflector, это подтверждается, частный метод AddIfNotPresent () содержит цикл while () для поиска точки вставки, используя обычный красно-черный обход узлов.

Эта ошибка с документом уже отправлена ​​ пользователем you-know-who.