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

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

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

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

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

MSDN