На самом деле это возможно за O (log n) в худшем случае, поскольку строки формируются из алфавита постоянного размера.
Вы можете выполнить 26 двоичных поисков для каждой строки, чтобы найдите самое левое вхождение каждой буквы. Если строки равны, то все 26 бинарных поисков дадут одинаковые результаты; либо то, что буква не существует ни в одной из строк, либо что ее крайнее левое вхождение одинаково в обеих строках.
И наоборот, если все двоичные поиски дают одинаковый результат, то строки должны быть равны, поскольку (1) алфавит фиксирован, (2) индексы крайних левых вхождений определяют частоту каждой буквы в строке, и (3) строки сортируются, поэтому частоты букв однозначно определяют строку.
Я предполагаю, что строки имеют одинаковую длину. Если это не так, то сначала проверьте это и верните False, если длины разные. Получение длины строки занимает O (1) раз.
Как отмечает @wim в комментариях, это решение нельзя обобщить до списков чисел; он работает только со строками. Когда у вас есть проблема алгоритми c, связанная со строками, размер алфавита обычно постоянен, и этот факт часто можно использовать для достижения лучшей временной сложности, чем это было бы возможно в противном случае.