Временная сложность алгоритма List.AddRange()

#c_sharp

Из названия понятна суть проблемы. Интересует какова временная сложность алгоритма
метода AddRange() списка в C#?
    

Ответы

Ответ 1

Из документации:


  Если List может вместить новые элементы без увеличения Capacity, этот метод
требует O(n) операций, где n — количество добавляемых элементов. Если для размещения
новых элементов приходится увеличивать емкость, этот метод становится O(n + m) операций,
где n — количество элементов для добавления и m — Count.


Ответ 2

Если при добавлении в список его вместимость capacity не нуждается в увелечении, то O(n)

В противном случае O(n + m), где n - количество добавленных элементов и m длина списка
перед добавлением

MSDN