Попытка заменить все пробелы одним пробелом

Вот еще один анализ, который показывает, что ваш алгоритм уже линейный.

Предположим, что у вас есть некоторый набор векторов, и алгоритм многократно выбирает два вектора из коллекции и заменяет их своим пересечением, пока там является одним вектором слева. Ваш метод подходит для этого описания. Я утверждаю, что любой такой алгоритм будет тратить, в общем, линейное время во всех исполнениях set_intersection.

Предположим, что set_intersection занимает не более A * (x + y) операции для векторов размера x и y.

Пусть K - сумма длин всех векторов в коллекции. Он начинается с размера ввода (n), и он не может опускаться ниже нуля, поэтому он может изменяться не более n.

Каждый раз, когда векторы размеров (x, y) комбинированное значение K уменьшается как минимум на (x + y)/2, так как результат должен быть короче, чем любой вход. Если мы суммируем это по всем вызовам, получим, что sum { (x + y)/2 } <= n, поскольку K не может измениться более чем на n.

Из этого можно получить sum { A * (x + y) } <= 2 * A * n = O(n). Левая сторона здесь - общее время, проведенное в set_intersection.

В менее формальном языке - потратить время x + y в set_intersection, вам нужно удалить как минимум (x + y)/2 элементы из вашей коллекции, так что расходы более чем за линейное время выполнения set_intersection заставит вас бежать из элементов.