HashSet и List в C# имеют разную вычислительную сложность для операций Contains и Add из-за различий в структуре данных.

HashSet использует хеш-таблицу, поэтому операции Contains и Add обычно выполняются за O(1) в среднем, так как поиск и вставка основаны на вычислении хеша и быстром доступе к бакету.
List — это динамический массив. Операция Contains требует перебора элементов, то есть O(n), так как нужно проверить каждый элемент до совпадения.
Добавление в List (Add) обычно O(1), если есть свободное место в массиве. Если массив заполнен, происходит расширение — выделяется новый массив большего размера, и все элементы копируются, что занимает O(n).

Почему List не просто массив?

List — это обертка над массивом с динамическим изменением размера. Массив в C# имеет фиксированную длину, которую нельзя изменить после создания. List управляет внутренним массивом и расширяет его по мере необходимости, предоставляя удобный интерфейс для добавления элементов.

Как List управляет размером?

При достижении текущей емкости List выделяет новый массив, обычно в 2 раза больше текущего, и копирует туда все элементы. Это уменьшает количество расширений при последовательных добавлениях.

Амортизированная сложность добавления в List:

Хотя отдельное добавление может быть O(n) при расширении, амортизированная сложность Add — O(1), так как расширения происходят редко и стоимость копирования распределяется на множество операций добавления.

Пример:

var list = new List<int>();
list.Add(1); // O(1)
bool contains = list.Contains(1); // O(n)

var set = new HashSet<int>();
set.Add(1); // O(1)
bool has = set.Contains(1); // O(1)