Изменения

Из построения понятно, что мы тратим <tex> O(n_k) </tex> на построение последнего каталога, <tex> O(n_{k-1} + n_k / 2) </tex> на построение предпоследнего и т.д. Пусть <tex> p = 2^{\lfloor log n \rfloor- 1} </tex>. Тогда получаем оценку <tex> O(n_k (1 + 1/2 + 1/4 + ... + 1/p) + n_{k - 1} (1 + 1/2 + 1/4 + ... + 1/(p/2)) + ... + n_1 ) </tex> <tex> = O(2 n_k + 2 n_{k -1} + ... n_1) = O(n) </tex> памяти. По алгоритму понятно, что такая же оценка верна и для времени на предподсчет.