О сложности сортировки булевой алгебры

Рассмотрен класс алгоритмов для нахождения порядка на $n$-элементном множестве, изоморфном булевой алгебре, путем последовательного попарного сравнения его элементов. Считается, что некоторые сравнения могут быть выполнены неправильно, причем общее число ошибочных сравнений не превосходит заданной величины $k(n)$. Показано, что если $k=o(\log n)$, то оптимальный алгоритм имеет ту же асимптотику сложности, что и оптимальный алгоритм при