Как сказал vivek_23, вы можете лучше использовать хеш-таблицу с высокой вероятностью.
Однако, чтобы достичь O (n log m ), и при условии, что ваши наборы хранятся в виде массивов, вы можете отсортировать A в O (m log m) время, а затем выполните n двоичный поиск для каждого элемента B , чтобы определить, находится ли он также в A . Каждый поиск занимает O (журнал м) время, всего O (n log м) время.
Итак, для A∪B вы можете скопировать A в новый набор C за O (м) времени. Затем для каждого элемента B вы выполняете поиск (двоичный поиск) на A. Если его нет в A, вы добавляете его в C. Таким образом, вы потратили бы O (m + n log м) время построения C и O (м log m) * для сортировки А. Так как m , общее время O (n log m) , как вы хотите.
Для A ∩ B вы начнете с пустого набора D . Для каждого элемента B вы выполняете поиск в A . Если он есть, вы добавите его к D . Когда вы закончите, вы выполните n поисков на A , всего (n log m) .
Если бы вы вставляли все элементы списка A в хеш-таблицу, а не сортировали их, вы могли бы делать все за O (m + n) время с высокой вероятностью.