Не-а. Проверка вхождения в хеш-таблицу выполняется за О(1) в любом случае.

> подразумевает перебор всех email в таблице которую пытаетесь получить.

Естественно нет. В этом и смысл хэш-таблицы, что поиск ключа работает за O(1) (в данном случае за O(длина строки), но длина строки * число строк это как раз размер инпута, так что все ок))

Если это кажется магией, то можно проще сделать.

Составим массив из пар (email, юзер) и отсортируем его.

Теперь если мы видим две идущих подряд пары вида (email, user1) и (email, user2), то добавляем ребро user1 <-> user2.

Итого получили честный O(n log n) (не линия конечно, но гораздо лучше квадрата)

А, судя по первому посту надо именно O(n). Тогда без хэш-таблицы, думаю, не обойтись.

а можно ссылку?

Реализации хеш-таблиц встроены почти во все языки. На чем вы пишете?

просто загугли что такое хэш таблица

java

Тогда используйте HashMap)

ну всё правельно сложность вставки в худщем случае составляет O(n)
для 1 элемента! а у нас n вставок

Сложность вставки и поиска в хеш-таблицах - О(1).

да откуда ты постоянно придумаешь, что "ну правильно"))))))

В среднем там O(1), и суммарно выйдет O(n)

Да, суммарно, для всех элементов выйдет O(n), то есть алгоритм отработает линейно

В случае с хэш-таблицами есть две причины, по которым запрос может работать долго.

1. Коллизии (несколько ключей с совпадающим или почти-совпадающим (в некотором смысле) хэшем). Вероятность коллизии стремится к 0 при росте n, поэтому асимптотику не портит. Если входные данные не специально подобраны или же параметры хэша выбираются случайно, то и на практике ничего плохого не случится.

2. Рост. Как и у обычного вектора, у таблицы есть некоторая емкость. Когда она заполнена, и снова делается вставка, то эта таблица растягивается в два раза, и все ключи повторно в нее вставляются. Но это вообще никак не портит асимптотику, потому что суммарно это будет стоить 1 + 2 + 4 + ... + n = 2n = O(n) на все n вставок.

Если ты хочешь алгоритм, который работает за линию детерминированно, то это надо уточнить отдельно. Но смысл такого требования сомнителен.

ну там вроде вместо ленивого перестроения активного хватит, чтобы убрать амортизацию

Амортизация тут не мешает вроде, онлайн-то не нужен.

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