text: Рекуррентное отношение для числа шагов может быть записано как T ( n ) = 2 T ( n 2 ) + O ( n ) {\displaystyle T(n)=2T({\tfrac {n}{2}})+O(n)} , которое может быть решено с помощью основной теоремы для рекурренции разделяй и властвуй, что даёт O ( n log ⁡ n ) {\displaystyle O(n\log n)} .