Читаю «Жемчужины проектирования алгоритмов».
В первой главе описывается проектирование алгоритма нахождения наименьшего отсутствующего числа:

minfree xs = minfrom 0 (lingth xs, xs)
minfrom a (n, xs) | n == 0     = a
                  | m == b - a = minfrom b (n - m, vs)
                  | otherwise  = minfrom a (m, us)
                  where (us, vs) = paition (<b) xs
                        b = a + 1 n div 2
                        m = length us

В резюме описана трудоёмкость в виде рекуррентной формулы:
T(n) = T(n div 2) + Θ(n)
И в виде прямой зависимости:
T(n) = Θ(n)
Вот этот переход и вызывает сомнения: не потерял ли автор log2(n)?
Т. е. ИМХО формула должна выглядеть так:
T(n) = Θ(n * log2(n))
Ведь операций мы делаем ровно в половину меньше чем при сортировке Хоара...