Итого: <tex>O(2^{2k}k) + O(\frac{n^3}{k})</tex>.
Приведем анализ выбора числа <tex>k</tex> для получения оптимальной сложности алгоритма.
В силу возрастания функции <tex>f(k) = 2^{2k}k</tex> и убывания функции <tex>g(k) = \frac{n^3}{k}</tex> имеем, что сложность будет оптимальна при таком значении <tex>k</tex>, что <tex>f(k) = g(k)</tex>. Прологарифмируем обе части этого равенства: <tex>k \ln 4 + \ln k= 3 \ln n - \ln k</tex> <tex>k = \frac{3 \ln n - 2 \ln k}{\ln 4} </tex> <tex> k Выбрав = 3 \log_4 n - 2 \log_4 k </tex> В силу того, что <tex> \log_4 k </tex> пренебрежительно мал по сравнению с <tex> k </tex> имеем, что <tex> k </tex> с точностью до константы равен <tex> \log n </tex> Таким образом, при подстановке <tex>k = \log n</tex>, получаем итоговую требуемую асимптотику <tex dpi=140>O(n^2 \log n) + O(\frac{n^3}{\log n}) = O(\frac{n^3}{\log n})</tex>
== Код алгоритма ==
<code>
