Computational complexity of operations: analyze the complexity of HashSet and List (Contains + Add) loops. Why is List not just an array? How does List manage its size? What is the amortized complexity of adding to a List?

HashSet and List in C# have different computational complexities for Contains and Add operations due to differences in data structures.

• HashSet uses a hash table, so Contains and Add operations are typically performed in O(1) on average, as search and insertion are based on hash calculation and quick access to buckets.

• List is a dynamic array. The Contains operation requires iterating over elements, which is O(n), as each element must be checked until a match is found.

• Adding to a List (Add) is usually O(1) if there is free space in the array. If the array is full, resizing occurs — a new larger array is allocated, and all elements are copied, which takes O(n).

Why is List not just an array?

List is a wrapper over an array with dynamic resizing. An array in C# has a fixed length that cannot be changed after creation. List manages an internal array and expands it as needed, providing a convenient interface for adding elements.

How does List manage size?

When the current capacity is reached, List allocates a new array, usually twice the size of the current one, and copies all elements into it. This reduces the number of expansions during successive additions.

Amortized complexity of adding to a List:

Although a single addition can be O(n) during resizing, the amortized complexity of Add is O(1), as expansions happen rarely and the cost of copying is spread over many add operations.

Example:

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)