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