Согласно документации ECMA для Set и Maps (http://www.ecma-international.org/ecma-262/6.0/index.html#sec -set-objects ):
Set объекты должны быть реализованы с использованием таблиц ha sh или другие механизмы, которые в среднем обеспечивают время доступа, которое сублинейно зависит от количества элементов в коллекции. Структуры данных, используемые в этой спецификации объектов Set, предназначены только для описания требуемой наблюдаемой семантики объектов Set. Он не предназначен для использования в качестве жизнеспособной модели реализации.
You will find similar sentences for Maps, WeakMaps and WeakSets. So, you should expect the time-complexity to be sublinear. Also, you can check out a solution on Javascript Вычислительная / временная сложность коллекций ES6