И всё-таки таким уж сложным он мне определённо не кажется. Если сравнить с классикой — оценкой снизу числа сравнений для задачи сортировки — то вроде отличие должно быть незначительным. Уж явно не в категории оценок сложностей арифметических задач...
