Изменения
→Схемная сложность
Каждый элемент <math>3\to2</math> имеет глубину <math>O(1)</math> и размер <math>O(n)</math>.
Подсчитаем количество элементов <math>3\to2</math>. На каждом шаге количество чисел, которые нужно просуммировать, уменьшается на в <math>1/3,{}5</math>раза. Тогда глубина дерева будет равна <math>\log_{3/2}n</math>, и в нём будет <math>n + \frac23n + \left(\frac23\right)^2n + \ldots = O(n)</math> элементов <math>3\to2</math>.
Тогда общая сложность равна
