Подбор констант

В корневой декомпозиции очень важен размер блока. Обычно брать s = $\sqrt{N}$ или близкое к ней число(желательно, чтобы делилось на максимально возможную степень двойки) оптимально, но сейчас мы поговорим об особых случаях. Пусть s - размер блока и мы знаем, что алгоритм работает за $O(N * s + \frac{N ^ 2 * \log(N)}{ s})$, тогда если взять s = $\sqrt{N} * 4$, то алгоритм будет работать быстрее, чем при s = $\sqrt{N}$, то есть при определении размера блока первым делом надо смотреть на асимптотику.

$O(n \sqrt{n \log n})$