What is the time complexity of concatenating two Hashsets together in C#?

Question

My confusion stems from the fact that most Hashset operations are O(1) time complexity but I was wondering if concatenating two hashsets like the following:

HashSet<T> firstSet = new HashSet<T> ();
HashSet<T> secondSet = new HashSet<T> ();

firstSet.Concat(secondSet);

is done in linear O(n) time or constant time.

I have checked official documentation and haven't had luck finding performance based specifications.

Answer 1

Concat is an extension method of Linq which is lazy, i.e. Linq does nothing when no action is required. That's why Concat itself has evident O(1) time complexity - Linq doesn't do anything:

// Note, that result is of IEnumerable<T> type
var result = firstSet.Concat(secondSet);

However, if we materialize result we'll have O(n) time complexity:

// result is HashSet<T>
var result = firstSet
  .Concat(secondSet)  // O(1)
  .ToHashSet();       // O(n)