Если нижняя граница для временной сложности задачи равна Ω(n^2), то это означает, что алгоритм, решающий эту проблему, должен занять как минимум C*n^2 время.
С другой стороны, у вас есть алгоритм, который занимает самое большее K*n*logn время.
Этот алгоритм не может работать дольше, чем nlogn. Вам нужен алгоритм, который запускается как минимум n^2 раз.
Таким образом, этот алгоритм не может решить эту проблему. Вы правы.